나무 수송

한 왕국의 대부분 지역은 강과 숲으로 이루어져 있다. 상류의 작은 강들은 서로 합쳐져 큰 강이 되고, 하류로 갈수록 다시 다른 강과 합쳐진다. 결국 모든 물길은 왕국 아래쪽의 바다로 이어지는 하나의 큰 강으로 모인다.

강가에는 나무꾼들이 사는 n개의 마을이 있다. 현재 목공소는 강의 최하류에 있는 왕국에만 하나 있다. 그래서 각 마을에서 벤 통나무는 강물에 띄워 최하류의 목공소까지 보내야 한다.

운송 비용을 줄이기 위해, 마을 중 k곳을 골라 목공소를 새로 지으려고 한다. 새 목공소가 생기면 상류에서 흘러온 통나무는 하류로 이동하다가 처음 만나는 목공소에서 처리된다. 목공소가 세워진 마을에서 생산된 통나무는 강으로 운반할 필요가 없다.

각 마을에서 한 해 동안 생산되는 통나무의 수와, 각 마을에서 하류 쪽으로 바로 이어지는 마을 또는 왕국까지의 거리가 주어진다. 강은 하류로 갈수록 합쳐지기만 하고 갈라지지 않으므로, 어떤 마을에서 왕국까지 가는 경로는 하나뿐이다.

통나무 하나를 강으로 1 km 운반하는 비용은 1이다. 통나무 2개를 5 km 운반하면 비용은 2 * 5 = 10이다. 전국의 총 운송 비용이 최소가 되도록 목공소를 지을 마을을 고르는 프로그램을 작성하시오.

첫째 줄에 왕국을 제외한 마을의 수 n과 새로 지을 목공소의 수 k가 주어진다. 마을은 1부터 n까지 번호가 붙어 있고, 왕국의 번호는 0이다.

다음 n개 줄의 i번째 줄에는 세 정수 w_i, v_i, d_i가 주어진다.

• w_i: 마을 i에서 생산되는 통나무의 수
• v_i: 마을 i에서 하류로 바로 이동했을 때 도착하는 첫 번째 마을 또는 왕국
• d_i: 마을 i에서 v_i까지의 거리

제한은 다음과 같다.

• 2 <= n <= 100
• 1 <= k <= 50
• k <= n
• 가능한 총 운송 비용은 2,000,000,000을 넘지 않는다.

새 목공소 k개를 최적으로 지었을 때, 모든 마을에서 생산된 통나무를 처음 만나는 목공소까지 운반하는 총 비용의 최솟값을 출력한다. 왕국에 있는 기존 목공소도 목적지가 될 수 있다.

그림이 주어진 경우, 선분은 강, 원은 마을을 나타낸다. 선분 위의 숫자는 그 구간의 거리이고, 원 안의 숫자는 마을 번호, 원 아래의 숫자는 해당 마을의 연간 통나무 생산량이다.

그림의 상황에서는 2번과 3번 마을에 목공소를 짓는 것이 최적이다. 그러면 4번 마을의 통나무를 2번 마을까지 보내는 비용 1 * 3과, 1번 마을의 통나무를 왕국까지 보내는 비용 1 * 1만 필요하다.