우주 정거장
시간 제한1초메모리 제한512 MB
가중치가 있는 트리에서 노드 1에서 시작해 모든 간선을 최소 한 번 지나고 돌아오는 최소 시간을 구한다. 임의의 두 모듈 사이를 이동하는 점프를 최대 M번 사용할 수 있고 점프 한 번의 비용은 K이다.
문제
Jones는 큰 꿈 중 하나를 이루었다. 국제 우주 정거장(ISS)으로 떠나는 다음 임무에 합류하게 된 것이다. 그는 이미 첫 번째 임무를 배정받았다. 우주 정거장에 탑재된 모든 전자 부품의 이상 여부를 점검하는 일이다.
ISS는 1번부터 N번까지 번호가 붙은 N개의 모듈로 이루어져 있다. Jones는 효율을 위해 정거장이 어떤 두 서로 다른 모듈 사이에도 단순 경로가 정확히 하나만 존재하도록 설계되었다는 사실을 알아냈다. 태양 플레어가 발생하면 서로 다른 두 모듈을 잇는 양방향 구간이 특히 방사선에 취약해진다. 구간 i를 점검하는 데는 정수 시간 Ci가 걸린다. Jones는 당연히 1번 모듈에서 출발해 모든 구간을 적어도 한 번씩 점검하고 다시 1번 모듈로 돌아오는 가장 빠른 경로를 찾으려 한다.
Jones는 두 모듈 사이의 직접 구간을 이용하는 것 외에도 우주복을 입고 정거장 밖으로 나가 아무 두 모듈 사이를 곧바로 이동할 수 있다. 다만 이런 이동은 M번까지만 할 수 있다. Jones는 우주복을 입고 한 모듈에서 다른 아무 모듈로 뛰어가는 데 항상 K의 고정된 시간이 걸린다고 가정한다.
입력
첫째 줄에는 테스트의 수 T가 주어진다. 각 테스트를 설명하는 첫째 줄에는 세 변수 N M K가 주어진다. (1 ≤ N, M ≤ 1000) 그다음 N–1개의 줄은 A B C 형태로 주어지며 (1 ≤ A ≤ B ≤ N; 0 ≤ C, K ≤ 106), A에서 B로 가는 직접 구간이 있고 그 구간을 점검하는 데 C 시간 단위가 걸린다는 뜻이다.
출력
i번째 줄에 i번째 테스트의 답을 나타내는 수 하나를 출력한다.