Одна сказочная страна располагалась в дельте далекой реки ( far away river ).
В стране было n островов и на каждом острове находился город. Города были соединены дорогами. Причем существовал в точности один путь от каждого города до любого другого, возможно проходящий через другие города. К сожалению мосты в этой стране были неизвестны, поэтому для пересечения реки использовались понтоны, поэтому путешествия были некомфортными, т.к. приходилось ездить только на лошадях. Когда было открыто мостостроительство король решил вместо нескольких понтонов построить мосты, по которым могли бы ездить даже кареты. В силу бедности страны только k мостов могут быть построены.
Вам необходимо выбрать какие k понтонов надо заменить на мосты так, чтобы суммарное время путешествия между всеми парами городов оказалось минимальным. Вы можете считать, что по обычным дорогам можно ехать только на лошади, а по дороге с мостом — только в карете, запряженной и несколькими лошадьми.
Входные данные
Первая строка входных данных содержит 4 числа n, k, sh и sc — число городов, число мостов, которым можно построить, скорость лошади и скорость экипажа в метрах в секунду (1 ≤ k < n≤ 10 000, 1 ≤sh; sc·≤ 100 000). Каждая из следующих n – 1 строк содержит три целых числа b
i, e
i — номера соединяемых городов и длину дороги в метрах l
i (1 ≤ l
i ≤ 10
6). Города пронумерованы от 1 до n, дороги пронумерованы от 1 до n – 1.
Выходные данные
k чисел — номера мостов, которые должны быть построены. Если существует несколько оптимальных планов строительства мостов, то выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2 1 2
1 2 5
3 2 6
1 4 4
4 6 4
4 5 5
|
1
3
|