Minimized Travel Distance with Limited Edge Swaps

WJJ wants to travel from village 1 (her home) to village N (her destination) through a network of M bidirectional roads connecting N villages. Each road i connects two villages A_i and B_i with an associated positive length C_i. The twist is that WJJ can perform a special magical operation at home up to K times before departing. In one operation she can choose any two roads (they can be anywhere in the world) and swap their lengths (i.e. if one road had length x and the other had y, after the swap one will have y and the other x). Note that the overall multiset of road‐lengths remains the same. Also note that swapping two roads of the journey (i.e. both on the travel path) is of no benefit since their contribution to the total distance will remain the same.

WJJ’s goal is to minimize the total distance she has to travel from village 1 to village N once she has performed at most K swaps. Assume that no other animal will change the roads later so that the only modifications are the ones she performs at home.

Observation: If WJJ chooses a path P (which is a sequence of roads from 1 to N) with an original total distance S and if she decides to swap a subset of the roads on this path, then the only beneficial swaps are when an edge on the path (with length w) is swapped with a road not on the path that has a smaller length, say c (with c < w). Since each swap is a transposition between one road on the path and one road off the path, at most K edges on the chosen path can be improved. In an optimal strategy for the path P, assume that WJJ swaps r roads (with r ≤ min(K, |P|)). Let the list of weights on the path be w₁, w₂, ..., w_|P| and let the candidate pool be the multiset of road lengths from the roads not in P. Then by pairing the largest edges on P with the smallest candidate values (provided the candidate is smaller than the edge’s original length) one can reduce the total cost by Σ (w - c) over the chosen swapped edges. The final distance along that path becomes:

Your task is to determine the minimum possible distance from village 1 to village N after performing at most K such swaps.

inputFormat

The input consists of:

1. A line containing three integers: N M K, where N is the number of villages, M is the number of roads, and K is the maximum number of road‐length swap operations allowed.
2. Then M lines follow, each containing three integers Ai Bi Ci indicating that there is a bidirectional road connecting villages Ai and Bi with length Ci.

It is guaranteed that from village 1 one can reach village N.

outputFormat

Output a single integer representing the minimum possible distance from village 1 to village N after at most K swap operations.

sample

3 3 1
1 2 5
2 3 10
1 3 20

5