X. Xtreme NP-hard Problem?!
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard 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.

Example
Input
6 6 3
1 2 3
2 3 1
3 6 4
1 4 1
4 5 5
5 6 9
Output
8