405146: GYM101806 X Xtreme NP-hard Problem?!
Description
Caution! This problem turned out to be NP-hard. But since there were no rules against writing an NP-hard problem, we decided to leave this problem here.
There is a bidirectional graph consisting of n vertices and m edges. The vertices and edges are numbered from 1 to n and 1 to m respectively, and the weight of edge i is wi. (1 ≤ i ≤ m) Given a natural number k, find the length of the shortest simple path that starts from vertex 1 and ends at vertex n, and consists of k edges. A simple path is a path that does not visit same vertex twice, and length of a path is the sum of weight of edges that consists the path.
InputIn the first line, three space-separated integers n, m, k are given. (2 ≤ n < 106, 1 ≤ m, k < 106, min(n, m, k) ≤ 5)
In the next m lines, three space-separated integers xi, yi, wi are given. They denote that edge i is connecting vertex xi and vertex yi, and has weight wi. (1 ≤ xi, yi ≤ n, 1 ≤ wi ≤ 108)
No loops or multiple edges are given.
OutputPrint the length of the shortest simple path that starts from vertex 1 and ends at vertex n, and consists of k edges. If there is no such path, print -1.
ExampleInput6 6 3Output
1 2 3
2 3 1
3 6 4
1 4 1
4 5 5
5 6 9
8