In an alternate universe where circuits are not cyclic, parts.'s project members had to work on an engineering project due the next day! They were given a blueprint which detailed the assembly of a circuit with
The blueprint contained steps which instructed the reader on how to assemble the circuit. Each step specified two parts and , which were to be connected with a wire of length .
Being smart students, they noticed that the blueprint was inefficient as it used a greater amount of wire to connect all components then what was needed. Therefore, in an attempt to conserve wire supplies, they decided to ignore some of the steps in the blueprint and follow the rest (such that all parts of the circuit are connected using minimum total wire length).
However,realized that there could be many combinations of steps that they could follow that would give them the minimum total wire length. Since his group members are lazy, your task is to help him determine which steps he has to follow and which ones he can ignore.
On one line, two space separated integers and , representing the amount of parts and steps specified in the blueprint.
The next lines each represent one step of the blueprint. Each line contains three space separated integers , and , representing a connection between parts and using a wire of length .
For each step of the blueprint, output
useful if the step has to be followed no matter how the circuit is configured,
so so if the step only has to be followed for some circuit arrangements, or
not useful if the step can always be ignored.
4 5 1 2 5 2 3 2 2 4 2 3 4 1 1 3 4
not useful so so so so useful useful
Explanation of Sample Output
The minimum length of wire needed to connect all parts is 7. To achieve this, steps 4 and 5 must always be followed, and step 1 can always be ignored. Steps 2 and 3 could be followed, depending on the circuit arrangement, but it is not guaranteed that they will be followed for all optimal circuit arrangements.