다리 놓기

먼 옛날, 어느 강의 삼각주에 한 나라가 있었다. 이 나라에는 $n$개의 섬이 있고, 각 섬에는 마을이 하나씩 있었다. 마을들은 도로로 연결되어 있었으며, 임의의 두 마을 사이에는 (중간 마을들을 거칠 수도 있는) 유일한 경로가 존재했다. 즉, 마을과 도로는 하나의 트리를 이룬다.

모든 도로는 강을 여울로 건넜다. 다리를 놓는 기술이 없었기 때문에 여울을 건너는 일은 불편했고, 오직 말을 타고서만 건널 수 있었다.

다리를 놓는 기술이 발견되자 왕은 일부 여울을 다리로 바꾸어 그 도로들을 더 편히 다닐 수 있게 하기로 했다. 다리가 놓인 도로는 마차로 건널 수 있다. 그러나 나라가 가난하여 다리는 $k$개만 지을 수 있다.

모든 마을 쌍 사이의 총 이동 시간이 최소가 되도록 다리를 놓을 $k$개의 도로를 골라야 한다. 다리가 없는 도로는 속도 $s_h$의 말로, 다리가 있는 도로는 속도 $s_c$의 마차로 이동한다(속도의 단위는 초당 미터). 길이 $l$인 도로 하나를 지나는 데 걸리는 시간은 말로는 $l / s_h$, 마차로는 $l / s_c$이다. 두 마을 사이의 이동 시간은 두 마을을 잇는 유일한 경로 위 도로들의 이동 시간의 합이며, 총 이동 시간은 서로 다른 모든 마을 쌍에 대한 그 값의 합이다.

첫째 줄에 네 정수 $n$, $k$, $s_h$, $s_c$가 주어진다. 각각 마을의 수, 지을 다리의 수($1 \le k < n \le 10\,000$), 말의 속도, 마차의 속도(초당 미터, $1 \le s_h, s_c \le 100\,000$)이다.

이어지는 $n - 1$개의 줄에는 각각 세 정수 $b_i$, $e_i$, $l_i$가 주어지며, 이는 도로 $i$가 잇는 두 마을과 그 도로의 길이(미터, $1 \le l_i \le 10^6$)를 뜻한다. 마을은 $1$번부터 $n$번까지, 도로는 주어지는 순서대로 $1$번부터 $n - 1$번까지 번호가 매겨진다.

총 이동 시간이 최소가 되도록 다리를 놓을 $k$개의 도로 번호를 출력한다. 한 줄에 오름차순으로, 공백 하나로 구분하여 출력한다.

총 이동 시간을 최소로 만드는 방법이 여러 가지라면 사전순으로 가장 작은 것을 출력한다. 즉, 각 방법에서 고른 도로 번호들을 오름차순으로 나열했을 때, 모든 최적해 중 사전순으로 가장 앞서는 수열을 출력한다.

그림은 예시 상황을 나타낸다.