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.

Input

• The first input line has two integers \(n\) and \(m\): the number of cities and flight connections. The cities are numbered \(1,2,\ldots,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.

Output

• Print \(n\) integers: the shortest route lengths from Syrjälä to cities \(1,2,\ldots,n\).

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)

Example

Sample input

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

Sample output

0 5 2