Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2677
Oil Deal

Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge

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.


There are several test cases in the input. The first line of each case contains n --- the number of nodes, m --- the number of pipelines, and s --- the amount of money terrorists have (2 <= n <= 50,000 , 1 <= m <= 100,000 , 0 <= s <= 1018 ). 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.

There is an empty line between cases.


On the first line of each case 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). There should be an empty line between cases.


6 7 10
1 2 3
1 3 3
2 3 3
3 4 1
4 5 5
5 6 4
4 6 5
1 5

Source: Andrew Stankevich's Contest #8
Submit    Status