Revamp the Trails

Farmer John wants to minimize the time taken to travel from pasture 1 to pasture N by revamping some of the trails into highways. When a trail is revamped, its traversal time becomes \(0\). Given the farm as a graph of \(N\) pastures connected by \(M\) bidirectional trails, each with a travel time, determine the minimum time required to travel from pasture 1 to pasture N if at most \(K\) trails can be revamped.

Input Constraints:

• \(1 \leq N \leq 10,000\)
• \(1 \leq M \leq 50,000\)
• \(1 \leq K \leq 20\)
• Each trail has endpoints \(P1_i\) and \(P2_i\) (\(1 \leq P1_i, P2_i \leq N\)) and a travel time \(T_i\) (\(1 \leq T_i \leq 1,000,000\)).

Task: Choose up to \(K\) trails to revamp (i.e. set their traversal time to \(0\)) in order to minimize the travel time from pasture 1 to pasture N. It is guaranteed that there exists at least one path from pasture 1 to pasture N.

Hint: Consider modifying Dijkstra's algorithm to keep track of the number of revamps used so far.

inputFormat

The input begins with a line containing three integers \(N\), \(M\), and \(K\), where \(N\) is the number of pastures, \(M\) is the number of trails, and \(K\) is the maximum number of trails that can be revamped.

This is followed by \(M\) lines, each containing three integers \(P1_i\), \(P2_i\), and \(T_i\) denoting a bidirectional trail between pastures \(P1_i\) and \(P2_i\) with traversal time \(T_i\).

outputFormat

Output a single integer representing the minimum time required to travel from pasture 1 to pasture N after optimally revamping at most \(K\) trails.

sample

3 3 1
1 2 2
2 3 2
1 3 5

0