402359: GYM100738 E Pretty Buses

In a country there are n cities connected by m roads. For each road, you have to pay a certain tax when you travel it.

The communication in the country is done by buses, which are driven by drivers. Initially, in city i, there is bus i which has driver i. In a bus there can be unlimited number of drivers. All drivers want to be in the same bus. For this, you can do two operations:

DRIVE b x y = the bus b is driven from city x to city y. You can perform this if bus b is initially in city x, the bus b has at least one driver and there is a road between x and y. The cost of this operation is the tax road of x-y.

MOVE d x y = the driver d moves from bus x to bus y. For this, driver d must be initially in bus x and bus x and bus y must be in the same city. The cost of this operation is 0.

Additionally, no driver can change the bus for more than 25 times.

Find the minimal cost to move all drivers into the same bus. Also, output a sequence of moves that obtains the cost.

The first line of the input contains numbers n and m(1 ≤ n ≤ 200000, 1 ≤ m ≤ 400000). Next m lines describe the roads by 3 integers: x, y and c, which means there is a road from x to y of tax c.

The first line of the output contains the minimal cost. Next lines contains the operations for obtaining the minimal cost, written in the format from the legend. When all operations are performed, output "Done".

3 3
1 2 1
1 3 1
2 3 2

2
Drive 2 2 1
Move 1 1 2
Drive 3 3 1
Move 3 3 2
Done

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

3
Drive 4 4 2
Move 2 2 4
Drive 4 2 1
Move 1 1 4
Drive 3 3 1
Move 3 3 4
Done