Szkolne Mistrzostwa W Programowaniu

Bajtogród stał się ostatnio bardzo niebezpiecznym miastem. Coraz częściej można tu spotkać piratów drogowych w ich szybkich, luksusowych samochodach. Jasiu ma dziś zakończenie roku szkolnego na 10:00, lecz ty jako jego rodzic boisz się go puścić samego do szkoły, aby przypadkiem niebezpieczny kierowca nie potrącił go podczas przechodzenia przez jezdnię na skrzyżowaniu. Niestety masz ważne spotkanie w firmie na 09:00 i nie możesz iść razem z nim. Postanawiasz wyznaczyć Jasiowi najbezpieczniejszą trasę do szkoły. Mianowicie taką, która zawiera najmniejszą ilość skrzyżowań, ale również i możliwie najkrótszy czas dojścia do szkoły.

Wejście

W pierwszej linii dwie liczby całkowite N i M oznaczające kolejno ilość skrzyżowań i ilość ulic w mieście. W kolejnych M wierszach po trzy liczby naturalne A, B i C, gdzie dwie pierwsze określają wzajemną relację połączenia danych skrzyżowań, natomiast trzecia jest to czas(w minutach) w jakim Jasiu jest  w stanie przejść daną ulicę. Poniżej dwie różne liczby D i S, określające skrzyżowanie przy którym znajduje się Dom i Szkoła. Zakładamy, że istnieje chociaż jedna droga, która łączy dom ze szkołą. Ponadto miasto ma spójny rozkład ulic.

Specyfikacja danych: Nϵ[1:10⁴],Mϵ[1:3*10⁶],Aϵ[1:10⁴],Bϵ[1;10⁴],Cϵ[1;20], Dϵ[1;10⁴],Sϵ[1;10⁴].

Wyjście

Godzina w formacie GG:MM o której Jasiu powinien najpóźniej wyjść z domu, aby zdążyć idealnie na zakończenie roku szkolnego. Zakłada się, że czasy wyjścia z domu i wejścia do szkoły są pomijalnie małe. Testy są tak dobrane, że wynik zawiera się tego samego dnia.

Przykład

Wejście:
5 6
1 5 10
5 4 10
1 2 5
2 4 3
1 3 8
3 4 12
1 4

Wyjście:
09:52

Wyjaśnienie

1->2 (5)

2->4 (3)

Łączny czas = (8)

10:00-00:08=09:52