Legal path

Given a directed graph ,every edge has a weight.
A legal route is defined as the list of edge, for every edge's weight should at least K greater than last edge's weight,if the last one exist. the length of a legal route is the total weight of the edge on it.
We should find the legal path from node $1$ to node $n$ of minimum length.

There is a number \(T\) shows there are T test cases below. ($T \leq 10$)
For each test case , the first line contains three integers $n , m , K$, $n , m$ means the number of nodes and the number of edges on the graph. In following there are $m$ lines. Each line has three integer $x , y , z$. indicate that there is an edge frome $x$ to $y$ weighted $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$

For each case ,if there is no legal path from $1$ to $n$, output -1 ,otherwise output the answer.

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

BestCoder Round #28