Kombajnista Ambroży nabroił w wiosce i teraz ucieka na swoim podrasowanym traktorze. Wioska składa się z n skrzyżowań, niektóre z nich są połączone dwukierunkowymi drogami. Skrzyżowania są ponumerowane liczbami od 1 do n, przy skrzyżowaniu o numerze 1 znajduje się karczma, skąd Ambroży ucieka. Ambroży stara się udać do swojej meliny, mieszczącej się przy skrzyżowaniu o numerze n, najszybszą możliwą drogą. Wypisz listę wszystkich skrzyżowań, na których Ambroży może pojawić się w drodze do swej meliny (czyli listę wszystkich skrzyżowań, które leżą na jakiejś najkrótszej ścieżce z skrzyżowania 1 do skrzyżowania n).
Pierwsza linia wejścia zawiera dwie liczby 2 <= n <= 100 000 i 1 <= m <= 200 000, oznaczające liczbę skrzyżowań i dróg w wiosce. Kolejne m wierszy zawiera opis kolejnych dróg: liczby całkowite a, b, c: 1 <= a, b <= n, 1 <= c < = 1000, oznaczające drogę między skrzyżowaniami a i b, którą kombajnista Ambroży przebywa w c sekund. Może istnieć wiele dróg łączących te same skrzyżowania, jak i droga pętelka (czyli a = b).
Należy wypisać listę wszystkich skrzyżowań, przez które może przejechać Ambroży, w kolejności rosnącej, po jednym w linii.
Dla danych wejściowych:
10 11 1 2 1 1 3 1 3 4 2 4 5 1 5 6 1 5 10 2 1 7 1 7 8 3 7 9 2 9 10 2 8 10 1
poprawną odpowiedzią jest:
1 7 8 9 10
Ambroży może pojechać 1-7-8-10 lub 1-7-9-10.
[Zgłoś rozwiązanie] [Moje zgłoszenia]