Час зустрічі (Срібло)

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

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

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

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