说明

注意！ 本题已被证明是 NP 难问题。但由于规则并未禁止出 NP 难问题，我们决定保留此题。

有一个包含 $n$ 个顶点和 $m$ 条边的无向图。顶点和边的编号分别从 $1$ 到 $n$ 和从 $1$ 到 $m$，边 $i$ 的权重为 $w_i$（$1 \le i \le m$）。给定一个自然数 $k$，请找到一条从顶点 $1$ 开始、到顶点 $n$ 结束、且恰好包含 $k$ 条边的最短简单路径的长度。简单路径是指不重复经过同一顶点的路径，路径的长度是组成该路径的所有边的权重之和。

输入格式

第一行包含三个由空格分隔的整数 $n$, $m$, $k$。

接下来的 $m$ 行，每行包含三个由空格分隔的整数 $x_i$, $y_i$, $w_i$。它们表示边 $i$ 连接顶点 $x_i$ 和顶点 $y_i$，且权重为 $w_i$。

输入中不包含自环或重边。

输出格式

输出一条从顶点 $1$ 开始、到顶点 $n$ 结束、且恰好包含 $k$ 条边的最短简单路径的长度。如果不存在这样的路径，输出 $-1$。

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

8

提示

数据范围

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

翻译由 DeepSeek V3.2 完成