Uolevi is working for a construction company that delivers pre-built components to the construction site. As the components can get very wide, it is important to know the maximum width limits for deliveries.

There are n locations numbered 1,2,\dots,n and m bidirectional roads numbered 1,2,\dots,m connecting them. The i-th road connects locations a_i and b_i and has width w_i. It is guaranteed that there exists a path between every pair of locations.

The construction company's factory is in location 1. Find the maximum delivery width that can reach each of the locations.

Input

The first line contains two integers n and m. The i-th of next m following lines contains three integers a_i, b_i, and w_i.

Output

Print the maximum widths that can reach the locations other than the factory in a line, separating with space, like below:

\textrm{ans}_1\qquad \textrm{ans}_2\qquad \dots\qquad \textrm{ans}_n

Constraints

• 2 \leq n \leq 10^5
• n-1 \leq m \leq 2 \times 10^5
• q \leq a_i < b_i \leq n
• (a_i, b_i) \neq (a_j, b_j) if i \neq j
• 1 \leq w_i \leq 10^9

Example 1

Input:

5 5
1 5 8
2 3 5
2 5 10
3 4 4
3 5 6

Output:

8 6 4 8

Example 2

Input:

10 15
1 2 6
1 5 5
2 3 5
2 6 9
2 7 2
3 4 1
3 5 10
3 7 6
3 9 3
4 10 1
5 6 3
5 9 5
6 8 2
6 9 1
7 8 2

Output:

6 5 1 5 6 5 2 5 1