小 $E$ 最近在学习次短路，决定进行一些创新。

在 $n$ 个点 $m$ 条边的正权有向图中，路径 $s$ 的长度 $d_s$，不再定义为路径上所有边的边权和。

而是，将路径上的边按照边权从大到小排序后，边权最大的 $k$ 条边，边权求和。如果路径不足 $k$ 条边，就将所有边求和。

在这样的新定义下，小 $E$ 要求你求出 $1$ 到 $n$ 的次短路。

设 $S$ 为所有 $1→n$ 的路径构成的集合，次短路定义为：

当 $|S|\leq 1$，输出 $−1$。
否则，$S$ 中的路径按照新定义的 $d_s$ 从小到大排序后，输出第二小的路径的 $d_s$。这里的次短路是非严格的，即可以出现和第一小的路径长度相等的情况。

为了简化问题，小 $E$ 将边权限制在 $\leq 10^3$ 的正整数。

输入格式

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。

对于每组测试数据：

第一行两个正整数 $n,m,k$，表示点数和边数，以及参数 $k$。

接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，表示 $u_i→v_i$ 边权为 $w_i$ 的有向边。

输出格式

对于每次询问输出一行一个整数，表示对应询问的答案。

样例

输入

2
6 7 2
1 2 1
1 3 3
2 4 3
2 5 2
3 5 5
5 6 5
4 6 4
3 2 1
1 2 1
2 3 1

输出

7
-1

提示

对于所有数据，$1\leq T\leq 5$，$2\leq n\leq 2\times 10^3$，$1\leq m\leq 5\times 10^3$，$1\leq u_i, v_i\leq n$，$1\leq w_i\leq 10^3$，$1\leq k\leq n$。