405146: GYM101806 X Xtreme NP-hard Problem?!

Memory Limit:1024 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

X. Xtreme NP-hard Problem?!time limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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.

ExampleInput
6 6 3
1 2 3
2 3 1
3 6 4
1 4 1
4 5 5
5 6 9
Output
8

加入题单

上一题 下一题 算法标签: