There are $n$ cities and $m$ flight connections between them. Your task is to determine the length of the shortest route from Syrjälä to every city.
The first input line has two integers $n$ and $m$ : the number of cities and flight connections. The cities are numbered $1,2,\dots,n$ , and city $1$ is Syrjälä.
After that, there are $m$ lines describing the flight connections. Each line has three integers $a$ , $b$ and $c$ : a flight begins at city $a$ , ends at city $b$ , and its length is $c$ . Each flight is a one-way flight.
You can assume that it is possible to travel from Syrjälä to all other cities.
Print $n$ integers: the shortest route lengths from Syrjälä to cities $1,2,\dots,n$ .
3 4 1 2 6 1 3 2 3 2 3 1 3 4· \n · · \n · · \n · · \n · · \n
0 5 2· · \n