A higher resolution is required to access the IDE
- 60
Statement
Goal
Edison is bringing electricity to N houses. He has already set up a power generator in house 1 and wants to connect it to the other houses. There are M pairs of houses that can be connected together, and we know how much making a link between each pair costs. Your job is to find which houses to link so that all the houses are connected to house 1 (directly or through other houses), while minimizing the total cost.* **there is always a solution that connects all houses**
* **the total distance from the generator to a house does not matter, as long as there is a path between them**
Input
Line 1: two integers, N and M, respectively the number of houses, and the number of connectable pairs
Next M lines three integers House1, House2 and Cost representing a possible connection between two houses
Next M lines three integers House1, House2 and Cost representing a possible connection between two houses
Output
Line 1: two integers, K and C, respectively the number of connections to make, and the total cost
Next K lines: the connections, as given, numerically sorted (on House1, then on House2)
Next K lines: the connections, as given, numerically sorted (on House1, then on House2)
Constraints
1 ≤ N ≤ 5000
0 ≤ M ≤ 50000
1 ≤ House1, House2, ≤ N
0 ≤ M ≤ 50000
1 ≤ House1, House2, ≤ N
Example
Input
3 3 1 2 1 2 3 99 1 3 7
Output
2 8 1 2 1 1 3 7
A higher resolution is required to access the IDE