FRAKTAL - konkurs programistyczny

NIKT SIĘ NIE RUSZA, TO JEST NAPAD!

Jaś został kierowcą grupy zajmującej się napadaniem na sklepy jubilerskie. To bardzo niebezpieczne zajęcie, ale równocześnie bardzo dochodowe.

Do zadań Jasia należy przygotowanie samochodu, czekanie pod sklepem z włączonym silnikiem a następnie brawurowa ucieczka przez miasto. Nasz bohater doskonale się do tego nadaje, ponieważ jest świetnym kierowcą. Zawsze gdy gdzieś jedzie, to wybiera najkrótszą drogę.

Plan akcji zakłada, że po wyjściu ze sklepu trzeba najpierw pojechać do tajnej kryjówki schować łupy, a dopiero potem, w innym wybranym miejscu porzucić samochód. Problem w tym, że w grupie nikt sobie nie ufa i o tym, gdzie jest kryjówka, wspólnicy dowiedzą się dopiero podczas akcji.

Jaś właśnie się zastanawia ile paliwa musi zatankować. Nie chce zatankować za dużo, bo przy obecnych cenach każda nadwyżka będzie go słono kosztować. Nie może też zatankować za mało, bo to by przekreśliło jego dalszą karierę kierowcy. Jaś wie, gdzie akcja się rozpocznie i gdzie ma porzucić samochód. Wie, że kryjówka może być w dowolnym miejscu w mieście. Nie wie tylko gdzie.

To twoje zadanie: Znając układ miasta, lokalizację sklepu oraz miejsca gdzie należy porzucić samochód, podaj ile co najmniej potrzeba paliwa, żeby mieć pewność, że podczas akcji będzie można dojechać do dowolnej kryjówki.

Wejście

Na wejściu znajdują się liczby: n, m (0 < n ≤ 10⁵, 0 < m ≤ 5*10⁵) oznaczające kolejno liczbę skrzyżowań oraz ulic w mieście. Następnie s, e (0 < s, e ≤ n) czyli numery skrzyżowań gdzie znajduje się sklep oraz gdzie należy porzucić samochód. Następnie m linii opisujące ulice w mieście. Każda ulica to trzy wartości: a, b - numery połączonych skrzyżowań oraz v - długość ulicy (0 < a, b ≤ n, a != b, 0 < v ≤ 10⁹).

Ulice są dwukierunkowe i się nie powtarzają. Z każdego punktu w mieście da się dojechać do wszystkich pozostałych.

Wyjście

Na wyjściu należy wypisać jedną wartość: minimalną ilość paliwa pozwalającą pomyślnie ukończyć akcję (zakładamy, że samochód spala jedną jednostkę paliwa na jedną jednostkę odległości).

Przykład

Wejście:

5 7
1 5
1 2 1
1 3 3
1 4 1
1 5 3
2 5 1
3 4 1
4 5 3

Wyjście:

6