고속도로 건설 계획

바이토시아의 군주 바이토사우루스 2세는 왕국의 교통 인프라를 개선하기 위해 고속도로 건설 계획을 세웠다.

바이토시아에는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 도시가 있다. 수도는 $1$번 도시이다. 도시들은 $m$개의 오래된 양방향 도로로 연결되어 있으며, 수도에서 다른 모든 도시로 이동할 수 있다. 이 계획은 오래된 도로 중 일부를 초고속 고속도로로 개량하여, 시민들이 고속도로만으로 모든 도시 쌍 사이를 오갈 수 있도록 하는 것이다.

문제는 간단하지 않다. 바이토사우루스 2세는 계획에 드는 금(비용)을 최대한 적게 쓰고 싶어 하기 때문이다. 게다가 걱정거리는 여기서 끝나지 않는다. 수도에서 시위가 일어났다. 주민들은 소음과 공해에 지쳐, 수도로 이어지는 고속도로를 최대 $d$개까지만 건설하는 데 동의한다.

수도 주민들의 요구를 만족하면서 고속도로 건설 계획을 실현하는 최소 비용을 구하여라.

첫째 줄에 세 정수 $n$, $m$, $d$ ($1 \le d \le n \le 2000$, $0 \le m \le n(n-1)/2$)가 주어진다. 각각 도시의 수, 오래된 도로의 수, 수도로 이어질 수 있는 고속도로 개수의 상한을 의미한다.

이어지는 $m$개의 줄에는 오래된 도로의 정보가 주어진다. 각 줄은 세 정수 $a$, $b$, $c$ ($1 \le a, b \le n$, $a \ne b$, $1 \le c \le 10^9$)로 이루어지며, 도시 $a$와 $b$가 오래된 도로로 연결되어 있고 이 도로를 비용 $c$로 고속도로로 개량할 수 있음을 뜻한다. 두 도시 사이를 직접 잇는 도로는 많아야 하나 존재한다.

고속도로 건설 계획의 최소 비용을 나타내는 정수 하나를 출력한다. 수도 주민들의 요구를 만족하는 계획은 항상 존재한다고 가정해도 된다.