문제

진흥이가 살고 있는 도시는 개의 마을로 이루어져 있으며, 이 마을들은 트리 구조로 도로가 연결되어 있습니다. 트리는 사이클이 없는 연결 그래프를 말합니다. 따라서 임의의 두 마을 사이에는 오직 하나의 경로만 존재합니다.

도시의 중심에는 번 마을이 있는데, 이곳은 모든 쌀을 모아두는 중앙 창고의 역할을 합니다. 나머지 번부터 번 마을까지는 각각 쌀을 생산하는 생산지입니다.

진흥이는 각 생산지를 방문해 그곳에서 생산된 쌀포대를 수거하여 번 마을의 중앙 창고로 운반해야 합니다. 하지만 진흥이가 한 번에 옮길 수 있는 양에는 한계가 있어, 한 번 이동할 때 최대 개의 쌀포대만 운반할 수 있습니다. 따라서 어떤 마을의 쌀포대를 모두 옮기려면 여러 번 오가야 할 수도 있습니다. 또한, 진흥이는 운반 중인 쌀포대를 잠시 다른 마을에 내려놓을 수도 있습니다.

각 마을 에는 개의 쌀포대가 있으며, 각 도로마다 이동하는 데 걸리는 시간이 분 단위로 주어집니다. 진흥이는 처음에 중앙 창고가 있는 번 마을에서 출발합니다. 쌀포대를 수거하거나 창고에 내려놓는 데 걸리는 시간은 없다고 가정합니다.

진흥이가 임무를 완수하기 위해 필요한 최소 시간을 분 단위로 출력하세요.

입력

첫 번째 줄에 양의 정수 과 가 공백으로 구분되어 주어집니다.

두 번째 줄에는 번 마을부터 번 마을까지 갖고 있는 쌀포대의 수 가 공백으로 구분되어 주어집니다.

다음 개의 줄에는 세 정수 가 공백으로 구분되어 주어집니다. 이는 마을 와 마을 를 연결하는 도로가 있으며, 그 도로를 이동하는데 분이 걸린다는 의미입니다. 주어지는 마을의 연결 형태를 나타내는 그래프는 트리임이 보장됩니다.

출력

진흥이가 모든 마을의 쌀포대를 중앙 창고로 옮기는 데 걸리는 최소 시간을 분 단위로 출력하세요.

채점

• 모든 에 대해서
• 모든 도로에 대해서

서브태스크