도로 포장

여러 도시와 양방향 도로가 있다. 1번 도시에서 N번 도시로 이동하려고 한다.

최대 K개의 기존 도로를 포장할 수 있다. 포장한 도로를 지날 때 걸리는 시간은 0이 된다. 어떤 도로를 포장할지 적절히 골라, 1번 도시에서 N번 도시까지 이동하는 데 필요한 최소 시간을 구하라.

입력은 항상 1번 도시에서 N번 도시까지 이동할 수 있도록 주어진다.

첫째 줄에 도시의 수 N(1 ≤ N ≤ 10,000), 도로의 수 M(1 ≤ M ≤ 50,000), 포장할 수 있는 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다.

다음 M개 줄에는 도로가 잇는 두 도시 a, b와 그 도로를 지나는 데 걸리는 시간 c가 주어진다. 모든 도로는 양방향이며, c는 1 이상 1,000,000 이하의 정수이다.

최대 K개의 도로를 포장하여 얻을 수 있는 1번 도시에서 N번 도시까지의 최소 이동 시간을 출력한다.