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.