Problem Description

Takahashi and Aoki decided to play a graph-based game to kill time.

The game consists of the following three steps:

• Aoki prepares a graph with $ N $ vertices and $ M $ edges. The vertices of the graph are numbered from $ 1 $ to $ N $, and the edges are numbered from $ 1 $ to $ M $. This graph does not contain multiple edges or self-loops.
• Aoki writes a distinct positive integer less than or equal to $ 10^9 $ on each edge.
• Takahashi writes a positive integer less than or equal to $ 10^9 $ on each vertex. Takahashi can write the same integer multiple times.

In the graph where Takahashi and Aoki have finished writing integers, an edge is called "lucky" if it satisfies the following condition:

• If the edge connects vertices $ u $ and $ v $, the integer written on the edge matches the smaller of the integers written on vertices $ u $ and $ v $.

Takahashi's score is the total number of "lucky" edges.

Given the graph in the state where Aoki has finished writing integers on the edges, find a way to write integers on the vertices such that Takahashi's score is maximized.

If there are multiple possible answers, output any one of them.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ u_1 $ $ v_1 $ $ a_1 $ $ u_2 $ $ v_2 $ $ a_2 $ : $ u_M $ $ v_M $ $ a_M $

• The first line contains the number of vertices $N\ (1\ ≦\ N\ ≦\ 40)$ and the number of edges $M\ (1\ ≦\ M\ ≦\ N×(N-1)/2)$ of the graph prepared by Aoki, separated by spaces.
• The next $ M $ lines, where the $ i $-th line contains the numbers of the two vertices $u_i,\ v_i\ (1\ ≦\ u_i\ ＜\ v_i\ ≦\ N)$ connected by the $ i $-th edge and the integer $a_i(1\ ≦\ a_i\ ≦\ 10^9)$ written on the edge, separated by spaces.
• The given graph does not contain multiple edges or self-loops.
• The values of $a_i(1\ ≦\ i\ ≦\ N)$ are distinct.

Output Format

The output consists of $ N $ lines. The $ i $-th line should contain the positive integer written on the $ i $-th vertex when Takahashi's score is maximized. Each integer must not exceed $ 10^9 $. End each line with a newline.

Sample Input and Output

Sample Input #1

8 7
1 2 1
2 3 3
3 4 2
4 5 7
5 6 4
6 7 6
7 8 5

Sample Output #1

1
3
4
2
4
9
6
5

Sample Input #2

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

Sample Output #2

7
6
11
9
17

Sample Input #3

12 14
1 2 14
1 3 6
3 5 11
2 5 10
2 3 1
3 6 13
2 6 8
8 10 2
7 9 12
10 11 3
8 9 9
6 10 4
6 7 7
9 12 5

Sample Output #3

14
15
6
1
10
8
14
9
12
4
3
5

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $1\ ≦\ N\ ≦\ 20$, you will be awarded $ 90 $ points.
• If you solve the dataset where $1\ ≦\ N\ ≦\ 40$, you will be awarded an additional $ 130 $ points. The total is $ 220 $ points.

Sample Explanation 1

Writing the integers as shown in the output example above, the $1,\ 2,\ 3,\ 5,\ 6,\ 7$ edges become "lucky". Therefore, Takahashi scores $ 6 $ points. There is no way to score more points.

Sample Explanation 2

The $4,\ 7,\ 9,\ 10$ edges become "lucky".

Sample Explanation 3

The graph is not necessarily connected.

见题面 Input 部分

见题面 Output 部分