Bobo has a connected undirected simple graph with n vertices and m edges.
The vertices are numbered by conveniently, and the i-th edge has weight .
For each integer , Bobo would like to choose a subset of edges to connect the vertices with each other.
The minimum sum of weight of valid subsets is denoted as f(k).
Find the value of .

输入描述:

The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains two integers n and m.
The i-th of the following m lines contains 3 integers ,  and  which denote the edge between vertices  and  with weight .

输出描述:

For each test case, print (n - 1) integers which denote .

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

2
3
3
1
3
6

备注:

* 
* 
* 
* 
* The number of test cases does not exceed 100.
* The number of test cases with n > 8 does not exceed 5.