405146: GYM101806 X Xtreme NP-hard Problem?!

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 w_i. (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.

In the first line, three space-separated integers n,  m,  k are given. (2 ≤ n < 10⁶, 1 ≤ m,  k < 10⁶, min(n,  m,  k) ≤ 5)

In the next m lines, three space-separated integers x_i,  y_i,  w_i are given. They denote that edge i is connecting vertex x_i and vertex y_i, and has weight w_i. (1 ≤ x_i,  y_i ≤ n, 1 ≤ w_i ≤ 10⁸)

No loops or multiple edges are given.

Print 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.

6 6 3
1 2 3
2 3 1
3 6 4
1 4 1
4 5 5
5 6 9

8