Problem description
Bajtozdrój to znany na całym świecie bajtocki kurort zawdzięczający swą famę pięknej lokalizacji i niespotykanym warunkom uzdrowiskowym. Pięknie położona w samym sercu Bajtogór miejscowość od lat kusi turystów doskonale utrzymanymi, profesjonalnie oświetlonymi, dobrze naśnieżonymi, starannie ubitymi, nie wyjeżdżonymi stokami narciarskimi, szeroką gamą kąpieli leczniczych w przystępnych cenach oraz słynną bazą hotelową - w tym luksusowym apartamentem, w którym zwykł spędzać najwspanialsze chwile sam król Bajtazar. Nadchodzi zima. Ciężkie chmury suną leniwie przez bezkresne przestrzenie niebios rozsiewając nad krainą Bajtazara pierwsze nasiona zimy, jesienne słoty powoli ustępują miejsca zimowemu puchowi, pierwsze kwiaty szronu rozkwitają na ekranach monitorów Bajtocjan, a obniżona temperatura ułatwia pracę komputerowym systemom chłodzenia procesorów.
Ciśnienie atmosferyczne spada do 997.5 hektopaskala, temperatura powietrza wynosi $\frac{-pi}{e}$. W związku z tym do Bajtozdroju napływają pierwsi turyści… Rada nadzorcza zarządzająca siecią hoteli w Bajtozdroju jest niezwykle przewidująca i nie da się zaskoczyć zimie i masom turystów. W celu predykcji translokacji czynnika ludzkiego do pomieszczeń mieszkalnych pozostających pod jurysdykcją Rady, rozpisano przetarg na wykonanie usługi polegającej na wyznaczeniu minimalnych odległości z każdego miasta Bajtocji do Bajtozdroju. Zwycięzca przetargu w dowodzie wdzięczności otrzyma z rąk samego przewodniczącego Rady dożywotni karnet na pobyt w wybranym przez siebie hotelu korporacji Bajtele-morele™ Jednak najwspanialszą nagrodą jest oczywiście uścisk ręki prezesa i świadomość dobrze wykonanego obowiązku obywatelskiego i przyczynienia się do poprawy sytuacji gospodarczo-społecznej rozwijającej się Bajtocji.
Wejście
W pierwszej linii wejścia dane są dwie liczby: N i M, oznaczające odpowiednio liczbę miast w Bajtocji oraz liczbę połączeń między miastami. Następnie danych jest M trójek liczb A, B, C. Każda trójka oznacza, że istnieje droga z miasta A do B, na której koszt przejazdu wynosi C. Oczywiście drogi w Bajtocji są jednokierunkowe (w przeciwieństwie do autostrad). Przyjmujemy, że Bajtozdrój ma numer 1.
Wyjście
Na wyjściu należy podać N − 1 liczb, gdzie i-ta liczba to minimalny koszt przejazdu do Bajtozdroju z miasta i + 1. Możesz założyć, że Bajtozdrój jest osiągalny z każdego miasta.
Ograniczenia
1 ≤ N, M ≤ 500 000, 1 ≤ A, B ≤ N, 0 ≤ C ≤ 109.
Przykład
| Input | Output | |
|
|