Road Paving

Time limit2sMemory limit128 MB

Summary

Find the minimum travel time from city 1 to city N when up to K roads can be paved to cost zero, using layered shortest-path search over (node, paves used).

Level: Medium6 of 10
Topics: Shortest path, Graph, Dynamic programming
Solved: No attempts yet

Problem

There are cities connected by bidirectional roads. You need to travel from city 1 to city N.

You may pave at most K existing roads. A paved road takes 0 time to traverse. Choose which roads to pave so that the travel time from city 1 to city N is as small as possible, and output that minimum time.

The input is always such that city N is reachable from city 1.

Input

The first line contains three integers N (1 ≤ N ≤ 10,000), M (1 ≤ M ≤ 50,000), and K (1 ≤ K ≤ 20): the number of cities, the number of roads, and the maximum number of roads that may be paved.

Each of the next M lines contains three integers a, b, and c, meaning there is a road between cities a and b that takes c time to traverse. All roads are bidirectional, and c is an integer between 1 and 1,000,000 inclusive.

Output

Output the minimum travel time from city 1 to city N after paving at most K roads.

Examples1

Example 1
Input
```
4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
```
Expected output
```
1
```