Час зустрічі (Бронза)

Бессі та її сестра Елсі хочуть дістатися від корівника до свого улюбленого поля. Вони хочуть вийти з корівника рівно в один і той самий час, а також прибути на улюблене поле рівно в один і той самий момент.

Ферма складається з $n$ полів, пронумерованих від $1\dots n$, де поле $1$ містить корівник, а поле $n$ є їхнім улюбленим полем. Ферма розташована на схилі пагорба, причому поле $x$ знаходиться вище за поле $y$, якщо x < y. Між деякими парами полів прокладено $m$ доріг. Однак, оскільки кожна дорога досить крута, по ній можна рухатися лише вниз по схилу. Наприклад, дорогу, що з'єднує поля $5$ та $8$, можна пройти з $5$ у $8$, але не можна пройти у зворотному напрямку, оскільки це потребувало б руху вгору по схилу. Між кожною парою полів існує не більше однієї дороги, тому m \leq n \cdot (n - 1) / 2.

Бессі та Елсі можуть витрачати різну кількість часу на проходження однієї й тієї самої дороги. Наприклад, Бессі може витратити $10$ одиниць часу, а Елсі — $20$. Крім того, час вони витрачають лише на рух по дорогах між полями. Оскільки вони дуже поспішають, проходження через будь-яке поле займає практично нульовий час, і вони ніколи не зупиняються та не чекають на полях.

Допоможіть визначити мінімальну кількість часу, необхідну Бессі та Елсі, щоб дістатися до свого улюбленого поля і прибути туди рівно в один і той самий момент.