Jump!#2366
Tiger loves to jump! However, jumping through the forest is not very convenient—there are potholes to trip over and trees to crash into. The clever and kind Rabbit decided to help Tiger by building several convenient roads out of yellow bricks (since yellow is Tiger's favorite color). To do this, Rabbit created a complete map of the Hundred Acre Wood and calculated which roads could be built and how many bricks would be needed for each. After evaluating the brick supplies, Rabbit realized that instead of some roads, it might be possible to build real forest highways—wide roads where Tiger could run faster and enjoy moving even more. To build a highway instead of a regular road, times more bricks are required, regardless of the road's location.
Each road connects two interesting places for Tiger—homes of the forest's inhabitants, clearings where he can jump, and so on. Rabbit numbered the interesting places with integers from to and listed the possible roads. Now he wants to build a road network such that the number of highways is maximized, but it is still possible to get from any interesting place to any other. For this plan, Rabbit has bricks available. Help him plan the road construction!
The first line of the input contains four integers , , , and (1 \leq n, m \leq 100000; 1 \leq k \leq 10^9; 1 \leq c \leq 1000)—the number of interesting places, possible roads, the total number of bricks available, and the factor by which a highway requires more bricks, respectively.
Each of the next lines describes a road with three integers a_i, b_i, l_i (1 \leq a_i, b_i \leq n; 1 \leq l_i \leq 10^6)—the numbers of the interesting places connected by the road, and the number of bricks needed to build this road.
Each road connects two different interesting places. There can be more than one road between two interesting places.
If it is impossible to build such a road network, print a single word Impossible.
Otherwise, print two integers and —the numbers of regular roads and highways in the optimal plan—on the first line. On the second line, print integers—the numbers of the regular roads to be built, in ascending order. On the third line print integers—the numbers of the highways, also in ascending order.
Roads are numbered as they appear in the input. If there are multiple optimal solutions, print any of them.
Example 1