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 a path exists between every pair of locations.

The construction company's factory is at location 1. For all other locations \ell = 2,3,\dots,n, find the maximum delivery width x_\ell that can reach location \ell.

Input

The first line contains two integers n and m. Each of the next m lines contains three integers a_i, b_i, and w_i.

Output

Print, on a single line, the maximum widths x_\ell for \ell = 2,3,\dots,n, separated by spaces.

Constraints

• 2 \leq n \leq 10^5
• n-1 \leq m \leq 2 \times 10^5
• 1 \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