不最近的路

Problem Description

小 E 最近在学习次短路，决定进行一些创新。 在 $n$ 个点 $m$ 条边的 正权有向 图中，路径 $s$ 的长度 $d_s$，不再定义为路径上所有边的边权和。 而是，将路径上的边按照边权从大到小排序后，边权最大的 $k$ 条边，边权求和。如果路径不足 $k$ 条边，就将所有边求和。 在这样的新定义下，小 E 要求你求出 $1$ 到 $n$ 的次短路。 设 $S$ 为所有 $1\to n$ 的路径构成的集合，次短路定义为：

• 当 $|S| \leq 1$，输出 $-1$。
• 否则，$S$ 中的路径按照新定义的 $d_s$ 从小到大排序后，输出第二小的路径的 $d_s$。这里的次短路是非严格的，即可以出现和第一小的路径长度相等的情况。 为了简化问题，小 E 将边权限制在 $\leq 10^3$ 的正整数。

Input

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

• 第一行两个正整数 $n,m,k$，表示点数和边数，以及参数 $k$。
• 接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，表示 $u_i\to v_i$ 边权为 $w_i$ 的有向边。

Output

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

Sample Input

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

Sample Output

7
-1

Hint

对于所有数据，$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$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（8）