0098. Tree

Input file name:	tree.in
Output file name:	tree.out
Time limit:	1 s
Memory limit:	64 megabytes

There grows a huge tree in China. No one knows when it had started to grow. For thousand years it grew and grew and now it has some branches accreted.

Because the tree is unique, a religious organization "St. Tree&Co." declared that it is a God's incarnation on the Earth. They have built a church nearby and protect this tree. But once the monks discovered that the tree became too heavy and can fall to the ground and die. They can't allow this to happen! So they decided to cut some accreted branches. They have found that each branch has one direction where the sap goes. Of course, each node (point of intersection of one or more branches) of the base tree configuration can get the sap from the roots. They have decided to leave all nodes (so that the visible size of the tree would remain unchanged). Of course the necessary configuration must also have a path from the roots to each node for the sap. Also the evident goal is to minimize the total weight of the tree (weight of each branch is known). Help the monks!

Input file

The first line of the input file contains two integer numbers: the number of nodes n (1 ≤ n ≤ 1000) and the number of branches in original configuration m (1 ≤ m ≤ 35000). m lines follow, each containing description of a single branch in form u_i v_i w_i meaning that i-th branch delivers the sap from node u_i to node v_i and weighs w_i (u_i ≠ v_i, 1 ≤ u_i, v_i ≤ n, 1 ≤ w_i ≤ 10⁷). Node 1 always describes the roots.

Output file

Output to the output file numbers of the branches left in an arbitrary order. The goal configuration must have minimal possible weight but still allow to deliver sap from the roots to any of n nodes. Duplication of branches' numbers in the output is not allowed!

Examples:

tree.in	tree.out
4 5 1 2 17 1 3 27 1 4 25 2 3 14 2 4 13	1 4 5

Source: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version