Bajtazar lubi sporty ekstremalne. Niedawno postanowił, by podczas najbliższej zimy zjechać ze szczytu Bajtogóry na sankach. Przygotował już mapę tras zjazdowych i zastanawia się, w jakim czasie może najszybciej przebyć drogę ze szczytu do podnóży Bajtogóry.
Na mapie jest zaznaczona pewna liczba punktów. Trasy zjazdowe składają się z odcinków jednakowej długości o końcach w zaznaczonych punktach. Jeden z końców każdego odcinka jest zawsze położony wyżej niż drugi. Odcinek można przejechać tylko w kierunku od wyższego końca do niższego. Dokładnie jeden z zaznaczonych punktów znajduje się na szczycie Bajtogóry. Punkty, z których nie prowadzą w dół żadne odcinki są punktami leżącymi u podnóża góry. Do każdego punktu można dotrzeć ze szczytu jadąc tylko po zaznaczonych na mapie odcinkach.
Bajtazar na swoich sankach może przejechać jeden odcinek w czasie będącym całkowitą, nie większą od 15, liczbą sekund. Każdy odcinek ma wyznaczony minimalny czas, w którym Bajtazar jest gotów go przejechać. Ograniczenia konstrukcyjne sanek powodują, że różnica czasów przejazdu dwóch kolejnych odcinków może wynosić co najwyżej trzy sekundy. Pierwszy odcinek na trasie Bajtazar przebywa powoli - zajmuje mu to 15 sekund.
Napisz program który
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite n i m, 2 <= n <= 100 000, 1 <= m <= 100 000 oznaczające odpowiednio liczbę punktów i odcinków na mapie. Punkty są ponumerowane od 1 do n. Punkt numer 1 znajduje się na szczycie góry. Kolejne m wierszy opisuje odcinki tras. W i+1 wierszu znajdują 3 liczby całkowite a, b i t, 1 <= a, b <= n, a =/= b, 5 <= t <= 15 oznaczające odpowiednio wyżej położony koniec, niżej położony koniec oraz minimalny czas przejazdu i-tego odcinka.
Twój program powinien wypisać na standardowe wyjście dokładnie jedną liczbę całkowitą równą minimalnemu czasowi zjazdu Bajtazara ze szczytu Bajtogóry.
Dla danych:
9 10 1 4 13 2 4 5 1 2 5 8 6 5 3 8 6 4 3 7 6 7 10 7 9 13 7 5 5 5 9 5
prawidłową odpowiedzią jest:
65
[Zgłoś rozwiązanie] [Moje zgłoszenia]