Мита-2

Нещодавно королева країни AlgoLand придумала новий спосіб відмивання грошей для свого королівського двору. Вона вирішила, що кожен житель, який бажає здійснити подорож з одного міста країни до іншого, повинен розплатитися за це бажання своїми грошима.

У країні AlgoLand є $N$ міст, пронумерованих від $1$ до $N$. Деякі міста з'єднані дорогами, рух по яких дозволено в обох напрямках. Починаючи рух по якійсь дорозі, мандрівник обов'язково повинен доїхати до її кінця.

Припустимо, що житель країни хоче здійснити подорож з міста $A$ у місто $B$. Новий указ королеви свідчить, що при проїзді по будь-якій дорозі країни під час цієї подорожі поліція може взяти з цього жителя мито на користь королівського двору (а може і не взяти). Якщо при цьому у жителя недостатньо грошей для сплати мита, то він автоматично потрапляє до в'язниці. Указ також встановлює розмір мита для кожної дороги країни. Оскільки королева піклується про жителів своєї країни, вона заборонила поліції брати з жителя мито більше двох разів під час однієї подорожі.

Зверніть увагу, що якщо існує кілька способів дістатися з міста $A$ до міста $B$, житель може самостійно обрати будь-який з них для своєї мандрівки.

Напишіть програму, яка:

• читає з вхідного файлу опис міст і доріг країни, а також початкове та кінцеве міста подорожі;

• визначає мінімальну суму грошей, яку мешканець повинен взяти, щоб гарантовано не потрапити до в'язниці під час поїздки;

та виводить результат у вихідний файл.