题目描述

Caution! This problem turned out to be NP-hard. But since there was no rules against writing a 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 \le i \le 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.

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

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

提示

Constraints

• $2 \le n < 10^6$
• $1 \le m, k < 10^6$
• $1 \le x_i, y_i \le n$
• $x_i \ne y_i$ ($1 \le i \le n$)
• $i \ne j \Rightarrow \{x_i, y_i\} \ne \{x_j, y_j\}$ ($1 \le i, j \le n$)
• $1 \le w_i \le 10^8$
• $\min(n,m,k)\le 5$