不最近的路

题目描述

给定一张有 $n$ 个点、$m$ 条边的正权有向图。

对于一条路径，把路径上的边按边权从大到小排序。若路径包含至少 $k$ 条边，则它的长度定义为最大的 $k$ 条边权之和；否则，它的长度定义为路径上所有边权之和。

考虑从顶点 $1$ 到顶点 $n$ 的所有路径。若这样的路径不超过一条，输出 $-1$；否则将这些路径按上述长度从小到大排序，输出第二条路径的长度。这里的次短路是非严格的，因此答案可以与最短路长度相等。

输入格式

第一行包含一个正整数 $T$，表示测试数据组数。

每组测试数据的第一行包含三个正整数 $n,m,k$，分别表示顶点数、边数和参数 $k$。

接下来 $m$ 行，每行包含三个正整数 $u_i,v_i,w_i$，表示一条从 $u_i$ 指向 $v_i$、边权为 $w_i$ 的边。

输出格式

对每组测试数据输出一行一个整数，表示对应答案。

样例输入 1

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

样例输出 1

7
-1

数据范围

$1\le T\le5$，$2\le n\le2\times10^3$，$1\le m\le5\times10^3$，$1\le u_i,v_i\le n$，$1\le w_i\le10^3$，$1\le k\le n$。