402987: GYM100960 I Equipment Assembling

Thousands of clones work at the biggest imperial factory which produces parts of stormtrooper equipment: blasters, body armors, helmets and so on. In the final step the equipment should be assembled using N pieces. Clones know M different methods of connecting one piece with another: the i-th method connects pieces a_i and b_i, and it takes t_i seconds.

When several pieces are connected together, they are considered a single unit, and it's no longer possible to connect any pair of them. Of course, it's not possible to connect pieces which belong to different parts of equipment, and it's always possible to assemble any part of equipment using these methods. A part is considered assembled if all the pieces of this part form a single unit, no matter how they are connected inside.

To increase productivity, it was decided that all parts have to be assembled in the fastest possible way. However, if the fastest way is not unique, then the resulting equipment can look differently. Two ways of assembling differ if the sets of applied methods of connecting differ. It's known that the army of clones looks awesome only if all the clones are identical. Because of that, the headmaster of the factory decided to retrain clones to apply some methods in different time so that the fastest way of assembling will be unique. Let's denote the new number of seconds needed to apply i-th method of connecting by t_i *  (note that for some i, the values of t_i and t_i *  may be equal). The time spent on method's application has to be an integer number of seconds and could not be negative.

However, retraining is a complex process, and it will take one day to change the time one method takes by one second. The headmaster asked you to compute the minimal possible number of days he needs to spend on retraining clones in order to make the fastest way of assembling unique.

The first line of input contains two integers N and M: the initial number of pieces and the number of connecting methods (1 ≤ N ≤ 20, 0 ≤ M ≤ 1000).

The next M lines contain information about methods of connecting two pieces. The i-th of them contains three integers a_i, b_i and t_i: the numbers of pieces that can be connected and the time this method takes (1 ≤ a_i, b_i ≤ N, a_i ≠ b_i, 1 ≤ t_i ≤ 10⁶).

On the first line, print a single integer: the minimal possible number of days the headmaster needs to retrain clones.

On the next M lines, print the descriptions of the new connecting methods: on the i-th of these lines, print three integers a_i, b_i and t_i * . The new connecting time t_i *  must be a non-negative integer not greater than 10⁹. The methods must be printed in the same order as in the input. It's guaranteed that there exists a solution that satisfies all the above constraints.

3 3
1 2 2
1 3 1
2 3 2

1
1 2 2
1 3 1
2 3 3

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

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