Algorytm Dijkstry

Limit czasu: 1s | Limit pamięci: 64MB

Dany jest graf ważony skierowany $G$. Wierzchołki oznaczamy liczbami od $1$ do $n$. Znajdź długości najkrótszych dróg z wierzchołka $1$ do wszystkich innych wierzchołków. Możesz założyć, że dla każdego wierzchołka $v$ istnieje droga łącząca $1$ z $v$.

Wejście

Pierwszy wiersz wejścia zawiera liczby $n$ i $m$, gdzie $n$ to liczba wierzchołków, a $m$ - liczba krawędzi. Każdy z kolejnych $m$ wierszy zawiera trójkę liczb $u$, $v$, $w$ opisującą krawędź: $u$ to wierzchołek początkowy krawędzi, $v$ - wierzchołek końcowy, a $w$ - waga krawędzi.

Wyjście

Pierwszy i jedyny wiersz wyjścia zawiara $n$ liczb: $v$-ta liczba, to minimalna odległość pomiędzy $1$ a $v$.

Ograniczenia

• $1 \le n \le 10^5$
• $1 \le m \le 2\cdot 10^5$
• $1 \le u, v \le n$
• $1 \le w \le 10^9$

Przykłady

Wejście 1

3 4
1 2 6
1 3 2
3 2 3
1 3 4

Wyjście 1

0 5 2