There are \(n\) schools and \(m\) teleportation connections between them. Your task is to determine the length of the shortest route from St. Robert to every school.

Input

The first input line has two integers \(n\) and \(m\): the number of schools and teleportation connections. The schools are numbered \(1,2,\dots,n\), and school \(1\) is St. Robert. After that, there are \(m\) lines describing the teleportation connections. Each line has three integers \(a\), \(b\) and \(c\): a teleportation connection begins at city \(a\), ends at school \(b\), and the time taken is \(c\). Each teleportation connection is one-way. You can assume that it is possible to travel from St. Robert to all other schools.

Output

Print \(n\) integers: the shortest route lengths from St. Robert to schools \(1,2,\dots,n\).

Constraints

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

Sample Input

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

Sample Output

0 5 2