Дешеве подорожування

Іван Скороход має оплатити зі своїх особистих коштів поїздку до місця наступного конкурсу з програмування. У нього є лише $s$ євро. Тому він ретельно вивчив розклад громадського транспорту та ціни. Позначимо $1$ як місце, де знаходиться Іван, $n$ — місце проведення конкурсу, а $2$, $3$, ..., n-1 — інші села, через які він може подорожувати. В Інтернеті Іван знайшов $m$ можливостей для подорожі у вигляді: автобус із села $v$ до села $w$ (і назад від $w$ до $v$) їде $t$ годин, а вартість становить $e$ євро в кожному напрямку. Між $v$ і $w$ може курсувати більше одного автобуса, причому різні автобуси можуть мати різний час у дорозі та різні ціни на квитки.

Напишіть програму, яка знайде маршрут з села $1$ до села $n$ за ціною, що не перевищує $s$ євро. Якщо існує кілька таких маршрутів, знайдіть той, на якому Іван проведе мінімальний час у дорозі.