When Bridge Building technology was discovered the king decided to build bridges instead of some fords to make roads easier to travel. Bridges would allow fords to be crossed even by carriages. The king liked the idea with bridges and ordered to build as many bridges as possible. Unfortunately, the country was quite poor, so only k bridges could be built.

The king asked you — his major advisor — to develop a bridge building plan. You have to choose k fords in such a way that the sum of travel times between all pairs of towns becomes as small as possible. You must assume that the ordinary roads would be traveled by horses, and roads enhanced with bridges would be traveled by carriages.

Input

The first line of the input contains four integer numbers: n, k, s_h and s_c —the number of towns in the country, the number of bridges to build (1 ≤ k < n ≤ 10000), the speed of the horse and the speed of the carriage in meters per second (1 ≤ s_h, s_c ≤ 100000).

Each of the following n - 1 lines contains three integer numbers: b_i, e_i —the towns connected by the road, and l_i —the road length in meters (1 ≤ l_i ≤ 10⁶). Towns are numbered from 1 to n, roads are numbered from 1 to n - 1.

Output

Output k numbers —the numbers of roads where the bridges should be built. If there are several possible optimal bridge building plans, output any of them.

Sample Input

6 2 1 2
1 2 5
3 2 6
1 4 4
4 6 4
4 5 5

Sample Output

1 3

Note: Special judge problem, you may get "Wrong Answer" when output in wrong format.