Oil Deal#5668
Oil is a very important strategic resource. Recently, the oil-rich country of Qari has decided to modernize and improve the efficiency of its oil transportation system. The system consists of pipelines that connect different nodes — oil extraction points, main country cities, and ports. The pipeline network is designed so that it is possible to transport oil from any node to any other node.
To ensure the reliability of the system and minimize possible downtimes, the engineering team has identified pipelines that can temporarily be taken offline for maintenance or upgrades. Each pipeline can be temporarily removed at a certain maintenance cost. The engineering team has a fixed maintenance budget and wants to select as many pipelines as possible for maintenance without exceeding the budget. However, the country still needs its oil distribution to function fully — after selected pipelines are removed for maintenance, the network must still remain connected so that oil can be transported between any pair of nodes.
For each pipeline, the cost required to take it offline for maintenance is known. Help the engineers determine which pipelines can be taken offline for maintenance to maximize their number, given the budget constraint, while still keeping the network fully connected.
The first line contains the number of nodes , the number of pipelines , and the available maintenance budget (2 \le n \le 50000, 1 \le m \le 10^5, 0 \le s \le 10^{18}).
The following lines contain information about the pipelines — for each pipeline, the numbers of the two nodes it connects and the maintenance cost (the cost does not exceed 10^9).
Oil can be transported along each pipeline in both directions, and each pair of nodes is connected by at most one pipeline.
On the first line, print the maximum number of pipelines the engineers can take offline for maintenance. On the second line, print the numbers of these pipelines (numbered according to their order in the input file, starting from ).
Example 1