P2939 [USACO09FEB] Revamping Trails G

Farmer John dutifully checks on the cows every day. He traverses some of the M (1

\* Line 1: Three space-separated integers: N, M, and K \* Lines 2..M+1: Line i+1 describes trail i with three space-separated integers: P1\_i, P2\_i, and T\_i

\* Line 1: The length of the shortest path after revamping no more than K edges

K is 1; revamp trail 3->4 to take time 0 instead of 100. The new shortest path is 1->3->4, total traversal time now 1.