Wielka Ucieczka Traktorem

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).

Wejście

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).

Wyjście

Należy wypisać listę wszystkich skrzyżowań, przez które może przejechać Ambroży, w kolejności rosnącej, po jednym w linii.

Przykład

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.