Relay Race: Shortest Path with Exactly k Edges

Cows are participating in a relay race on a pasture represented by an undirected connected graph. Each edge (trail) connects two distinct intersections and has an associated positive length. Given the starting intersection S and the ending intersection E, your task is to compute the shortest path (minimum total length) that uses k edges exactly. That is, if the path is represented as a sequence of vertices \(v_0, v_1, \ldots, v_k\) with \(v_0 = S\) and \(v_k = E\), then you need to minimize the cost defined by:

[ \text{Cost} = \sum_{i=1}^{k} w(v_{i-1}, v_i), ]

If no such path exists, output -1.

inputFormat

The input begins with a single line containing five space separated integers:

• V: the number of intersections (vertices) (1 ≤ V ≤ 1000)
• M: the number of trails (edges) (2 ≤ M ≤ 100)
• k: the exact number of edges that must be used (2 ≤ k ≤ 1,000,000)
• S: the starting intersection (1 ≤ S ≤ V)
• E: the ending intersection (1 ≤ E ≤ V)

Each of the next M lines contains three space separated integers u v w, describing an undirected edge between intersections u and v with length w (1 ≤ w ≤ 1000). It is guaranteed that no two intersections are directly connected by more than one trail and that every intersection has degree at least 2.

outputFormat

Output a single integer representing the length of the shortest path from S to E that consists of exactly k edges. If no such path exists, output -1.

sample

3 3 2 1 3
1 2 5
2 3 7
1 3 20

12