Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SMWP_117 - Niebezpieczna Droga

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:104],Mϵ[1:3*106],Aϵ[1:104],Bϵ[1;104],Cϵ[1;20], Dϵ[1;104],Sϵ[1;104].

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

 


Dodane przez:Bartosz Rychcik
Data dodania:2016-05-25
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:Szkolne Mistrzostwa W Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.