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

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

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

Зазначимо, що якщо існує кілька способів потрапити з міста \(A\) до міста \(B\), то мешканець може вибрати для подорожі будь-який із них за власним бажанням.

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

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

Формат вхідних даних

Перший рядок містить числа \(𝑁\) і \(𝑀\) (\(2≤𝑁≤10000\) , \(1≤𝑀≤100000\) ), розділені пробілом - кількості міст та доріг.

Наступні рядки описують дороги. Кожен з цих рядків описує одну дорогу і містить три числа \(𝑋 , 𝑌 , 𝑍\) (\(1≤𝑋,𝑌≤𝑁 \); \(𝑋≠𝑌\) ; \(1≤𝑍≤200000000\) ), розділених пробілами, що означають, що за її проїзд треба сплатити \(𝑍\) грошових одиниць.

Останній рядок містить числа \(𝐴\) та \(𝐵\) (\(1≤𝐴,𝐵≤𝑁\) ; \(𝐴≠𝐵\) ) — номери початкового та кінцевого міст подорожі.

Гарантується, що існує хоча б один спосіб проїзду з \(𝐴\) до \(𝐵\) .

Формат вихідних даних

Єдиний рядок вихідного потоку повинен містити одне число, що дорівнює мінімальній сумі грошей, яку повинен взяти з собою мешканець, щоб мати можливість здійснити подорож із міста \(A\) до міста \(B\) і при цьому гарантовано не потрапити до в'язниці незалежно від дій поліцейських.

Приклад вхідних даних

5 6
1 2 10
1 3 4
3 2 3
1 4 1
4 5 2
5 2 3
1 2

Приклад вихідних даних

3