농부 태웅이는 아버지 일을 물려받아 성실하게 소를 키우고 있다.

목초지 사이에는 M(1 ≤ M ≤ 50,000)개의 길이 존재하며,

그 길을 따라 1번 목초지에서 N번 목초지로 이동해야 한다. (이동이 불가능한 경우는 주어지지 않는다)

태웅이의 농장에는 N(1 ≤ N ≤ 10,000)개의 목초지가 있으며, 각각 1번부터 N번까지 번호가 매겨져 있다.

현재 이 목초지들은 양방향 비포장 길로 연결되어 있다.

각 길 i는 목초지 P1_i와 P2_i(1 ≤ P1_i ,\ P2_i ≤ N)를 연결하며, 이동하는 데 T_i(1 ≤ T_i ≤ 1,000,000)만큼의 시간이 걸린다.

게으른 태웅이는 긴 이동 시간을 줄이기 위해 일부 길을 정비하려고 한다.

최대 K(1 ≤ K ≤ 20)개의 길을 선택하여 고속도로로 바꾸면, 해당 길의 이동 시간이 0이 된다.

태웅이가 최소 시간으로 이동할 수 있도록 길을 정비해주자.

길 정비하기 timer 2s memory 256MB

길 정비하기 2s 256MB