페테르부르크에서 모스크바까지

2112년 세계 프로그래밍 컵을 치르려고 러시아의 유럽 지역에 유료 도로망을 새로 깔았다. 이 도로망은 도시 $n$개를 잇는 양방향 도로 $m$개로 이루어진다. 각 도로는 서로 다른 두 도시를 직접 잇고, 같은 도시 쌍을 잇는 도로는 둘 이상 없으며, 이 도로망만 써서 어느 도시에서 어느 도시로든 갈 수 있다. 요금 정산을 편하게 하려고 두 도로가 도시 밖에서 교차하지 않도록 놓았다.

도로마다 양의 정수 요금이 정해져 있다. 원래는 운전자가 유료 도로를 이용하면 지나간 도로의 요금을 모두 더한 금액을 낸다. 두 수도를 오가는 자동차 여행을 늘리려고 운영사 Radishchev는 특별 할인을 내놓았다. 상트페테르부르크에서 모스크바로 가는 여행이라면 경로에서 가장 비싼 도로 $k$개의 요금만 내면 된다.

정확히 말하면 경로가 도로 $l$개로 이루어져 있다고 하자. 경로에서 가장 비싼 도로의 요금을 $c_1$, 두 번째로 비싼 도로의 요금을 $c_2$라 하는 식으로 두면 $c_1 \ge c_2 \ge c_3 \ge \dots \ge c_l$ 이 된다. $l \le k$ 이면 경로가 짧아서 할인이 없고 운전자는 평소처럼 $\sum_{i=1}^{l} c_i$ 를 낸다. $l > k$ 이면 가장 비싼 도로 $k$개의 요금, 즉 $\sum_{i=1}^{k} c_i$ 만 낸다.

Radishchev의 수석 분석가가 되어 상트페테르부르크에서 모스크바까지 가는 가장 싼 여행 비용을 구하라.

첫째 줄에 정수 $n$, $m$, $k$ ($2 \le n \le 3000$, $1 \le m \le 3000$, $1 \le k < n$)가 주어진다. 각각 도시의 수, 도로의 수, 한 번의 여행에서 요금을 내는 도로의 최대 개수이다.

다음 $m$개 줄에 도로 정보가 주어진다. $i$번째 줄에는 정수 $u_i$, $v_i$, $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le w_i \le 10^9$)가 주어지며, 도시 $u_i$와 도시 $v_i$를 잇는 양방향 도로의 요금이 어느 방향으로 가든 $w_i$라는 뜻이다. 같은 도시 쌍을 잇는 도로는 많아야 하나이고, 주어진 도로만 써서 모든 도시 사이를 오갈 수 있다.

1번 도시(상트페테르부르크)에서 $n$번 도시(모스크바)까지 가는 최소 여행 비용을 정수 하나로 출력한다.