注意！这个问题结果是 NP-hard 的。但由于没有规则禁止出 NP-hard 的题目，我们决定把这道题留在这里。

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

输入格式

第一行包含三个空格分隔的整数 $n$，$m$，$k$。（$2 \le n < 10^6$，$1 \le m, k < 10^6$，$\min(n, m, k) \le 5$）

接下来的 $m$ 行，每行包含三个空格分隔的整数 $x_i$，$y_i$，$w_i$。它们表示边 $i$ 连接顶点 $x_i$ 和顶点 $y_i$，且权重为 $w_i$。（$1 \le x_i, y_i \le n$，$1 \le w_i \le 10^8$）

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

输出格式

输出从顶点 $1$ 开始、在顶点 $n$ 结束，且由 $k$ 条边组成的最短简单路径的长度。如果不存在这样的路径，则输出 -1。

样例

输入样例 1

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

输出样例 1

8