rebuild

All roads of Byteland have been destroyed by a recent epic fight between good and evil. Unfortunately, the citizens need to get back to work and need to rebuild their road network.

There are n interesting points in the city, and there are m proposals for roads to build between the points. The i-th proposal is to build an undirected road between the ai-th point and the bi-th point with a cost of ci.

The city would like to build a set of roads such that it's possible to go from any one interesting point to any other interesting point through some series of built roads. They know that at least one such set of roads exists. If there are multiple sets of roads that satisfy the condition, they would like to find a set that minimizes the total cost of roads built. If there are multiple sets with minimum total cost, they will break ties in a process described in the next paragraph.

In the process of rebuilding, the city would also like to lower congestion in some points. More specifically, if there are multiple sets of roads with the same minimum cost, they would like to choose a set that minimizes the number of roads incident to the first interesting point (while keeping the cost minimum). If there are still ties, they would like to minimize the number of roads incident to the second interesting point (while keeping the cost and the number of roads incident to the first interesting point to be small). This continues on until the last interesting point.

More formally, we can say the degree sequence of a set of roads is the sequence {deg(1),deg(2),...,deg(n)}, where deg(i) is the number of roads incident to the i-th interesting point. Given two sets of roads R1,R2 that each connect all the points, we can say the city prefers R1 to R2 if R1's cost is strictly smaller than R2's cost, or R1 and R2 costs are equal and the degree sequence of R1 is lexicographically smaller than the degree sequence of R2. 

Given n and the description of the m proposals of roads, print the minimum cost of a set of roads that connects the points and the degree sequence of that set of roads.

Input Format
The first line of the input will contain an integer T, denoting the number of test cases.
Each test case will be formatted as follows:
The first line of the test case will contain 2 integers, n, m.
Then m lines will follow, each with 3 integers ai, bi, ci.

Output Format
Print two lines for each test case.
The first line contains the minimum cost of a set of roads that connects all the points.
The second line contains n space separated integers, the degree sequence of the set of roads chosen. The i-th number on this line represents the number of roads incident to the i-th interesting point. 

Constraints
For all files
1 ≤ T ≤ 5
1 ≤ ai, bi ≤ n 
1 ≤ ci ≤ 1,000,000,000 
n-1 ≤ m ≤ 100,000 

File 1 -- 40 pts:
2 ≤ n ≤ 50
All road costs are distinct.

File 2 -- 30 pts:
2 ≤ n ≤ 50
All road costs are equal to 1.

File 3 -- 20 pts:
2 ≤ n ≤ 50

File 4 -- 10 pts:
2 ≤ n ≤ 50,000

SAMPLE INPUT
3
5 7
2 5 7
1 4 3
2 3 5
1 3 2
1 5 4
3 4 6
1 2 1
4 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 1 1000000000
1 1 1
2 3 1000000000
6 7
1 2 1
2 3 1
3 1 1
4 5 2
5 6 2
6 4 2
1 4 100000

SAMPLE OUTPUT
10
4 1 1 1 1
3000000000
1 1 2 2
100006
2 1 2 2 1 2

Explanation

For the first sample case, there are 5 interesting points and 7 roads. There is only one set of roads that connects all the points and has minimum cost 10. That is, we can choose the roads {1-2, 1-3, 1-4, 1-5} which connects all the cities for a cost of 1+2+3+4=10. The degree sequence of this set of roads is {4,1,1,1,1}.

For the second sample case, watch out for integer overflow. Note that it's possible for a proposal to connect a point to itself. In addition, it may be possible to have multiple proposals between a pair of points.

For the third case, there are multiple sets of roads that connect the points with cost 100006. For example, the roads {2-3, 3-1, 5-6, 6-4, 1-4} have cost 100006 and connect all the points. However, the degree sequence of this set of roads is {2,2,1,2,2,1}. We can instead choose the set {2-3, 3-1, 5-6, 6-4, 1-4} for the same cost and with a degree sequence of {2,1,2,2,1,2} which is lexicographically smaller.

Difficulty: EASY
Tags: Spanning trees

Starter code:

Solutions: