问题描述
一个有向图，给定起点终点，每条边上有权值。
一条合法的路径定义为相邻边的权值之差不小于$K$的路径，即路径上每条边的权值至少要比上一条边的权值大$K$，如果上一条边存在。合法路径的长度定义为路径上的边权值总和。
求从起点到终点的合法路径的最短长度。
输入描述
有多组数据，第一行为数据组数$T$（$T \leq 10$）。
对于每组数据，第一行为三个整数$n,m,K$，$n,m$分别表示这组数据的有向图的点数，边数，起点为$1$号点，终点为$n$号点。
在接下来有$m$行，每行有三个整数$x,y,z$，表示从$x$到$y$有一条权值为$z$的边。
$2 \leq n \leq 100,000$
$0 \leq m \leq 200,000$
$1 \leq K,z \leq 1,000,000,000$
$1 \leq x,y \leq n$
输出描述
对于每组数据，如果不存在从起点到终点的合法路径，输出-1。
否则输出合法路径的最短长度。
输入样例
3
3 2 1
1 2 1
2 3 2
3 2 1
1 2 2
2 3 1
4 6 2
1 2 1
1 2 2
2 3 3
1 3 5
2 4 2
3 4 7
输出样例
3
-1
11
