Spanning Tree + DSU

Oil Deal

Oil is a very important strategic resource. Recently United States of Antarctica invaded the rich in oil country of Qari, and now try to keep the control of the oil transportation system. The system consists of pipelines that connect different nodes - oil sources and main country cities and ports. It is designed in such a way that it is possible to transport oil from any node to any other one.

However the resisting native forces of Qari are not satisfied with the situation. So they continuously perform terror acts, blowing up some oil pipelines. Recently terrorists have decided to perform a series of explosions and want to hurt the oil pipeline system as much as possible.

For each pipeline the terrorists know the cost of blowing it up. They have a fixed sum of money and want to explode as many pipes as possible for this sum. However, since they still need oil for themselves in different regions of the country, they want the system still be able to transport oil from any node to any other one. Help them to find out which pipes to blow up.


The first line contains the number of nodes n, the number of pipelines m, and the amount of money s terrorists have (2n50000, 1m100000, 0s1018). The following m lines contain information about pipelines - for each pipeline the nodes it connects and the cost of blowing it up is specified (cost does not exceed 109).

Oil can be transported along each pipeline in both directions, each two nodes are connected by at most one pipeline.


On the first line print the maximal number of pipelines terrorists can blow up. On the second line print the numbers of these pipelines (pipelines are numbered starting with 1 as they are listed in the input file).

Time limit 1 second
Memory limit 64 MiB
Input example #1
6 7 10
1 2 3
1 3 3
2 3 3
3 4 1
4 5 5
5 6 4
4 6 5
Output example #1
1 5
Source 2004 Petrozavodsk, Summer, Andrew Stankevich Contest 7, August 22, Problem H