Road Paving

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.

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 the minimum travel time from city 1 to city N after paving at most K roads.