Maximizing the Shortest Path Length by Deleting Edges

You are given an undirected graph \(G\) with positive edge weights, which is connected between node 1 and node \(N\). You are allowed to delete at most \(K\) edges from the graph. Your task is to delete a set of edges (possibly empty, but at most \(K\) edges) such that after deletion:

1. Nodes 1 and \(N\) remain connected.

2. The shortest path distance between nodes 1 and \(N\) is as large as possible.

Note: It is guaranteed that the original graph is connected between 1 and \(N\).

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\) where \(N\) is the number of nodes, \(M\) is the number of edges, and \(K\) is the maximum number of edges you can delete.

Each of the next \(M\) lines contains three integers \(u\), \(v\), and \(w\) indicating that there is an undirected edge between nodes \(u\) and \(v\) with weight \(w\). It is guaranteed that \(w > 0\).

Constraints (for practical solutions): \(N \le 10\) and \(M \le 20\).

outputFormat

Output a single integer representing the maximum possible shortest path distance between node 1 and node \(N\) after deleting at most \(K\) edges while keeping nodes 1 and \(N\) connected.

sample

4 4 1
1 2 3
2 4 3
1 3 4
3 4 4

6