#1502. [L2-4] 春节路线

春节返乡高峰期间，你要从城市 $1$ 驾车前往城市 $n$。道路构成一张 $n$ 个点、$m$ 条双向道路的图，每条道路都有一个正整数通行耗时。

由于车流量激增，自信的你预测：司机会优先选择“足够快”的路线，从而造成某些路段拥堵。定义：

• 设在原图中从 $1$ 到 $n$ 的最短通行时间为 $D$（若不可达则视为无穷大）；
• 给定参数 $k$，任何总耗时 不超过 $D + k$ 的从 $1$ 到 $n$ 的路线都会被大量司机选择并拥堵；
• 为了完全避开这些拥堵路段，你选择的路线必须满足：
  你路线中的每一条道路，都不能以相同的经过方向出现在任何一条总耗时 $\leqslant D + k$ 的 $1 \to n$ 路线中。
  （也就是说，只要某条道路在某条“足够快”的路线里出现过并且经过这条路径的方向一致，这条路线就禁止使用。）

在满足上述避堵规则的前提下，请求出你仍然能够到达城市 $n$ 时的最短通行时间；若无法到达，则输出 $-1$。

第一行三个整数 $n, m, k$。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示两条有向边 $(u, v)$ 和 $(v,u)$，通行耗时均为 $w$。

输出一个整数：

若存在满足避堵规则的路线，输出其最短通行时间；

否则输出 $-1$。

样例输入 1

4 5 0
1 2 1
2 3 1
3 4 1
1 3 3
2 4 3

样例输出 1

7

样例输入 2

10 20 2
1 4 6
5 7 7
3 6 6
3 5 12
1 5 7
4 7 12
8 10 7
8 9 8
5 10 12
5 6 9
3 9 10
5 8 12
4 5 12
9 10 6
1 6 3
6 8 8
4 6 8
1 10 6
6 7 11
4 10 4

样例输出 2

10

样例解释 1

最短路为 $1 \to 2 \to 3 \to 4$，被限制，但还可以走 $1 \to 3 \to 2 \to 4$，时长为 7。

因为 $(2,3)$ 只认为 $2\to 3$ 堵车，但 $3\to 2$ 不堵。

$2 \leqslant n,m \leqslant 5 \times 10^5$

$1 \leqslant u, v \leqslant n$ 且 $u \neq v$

$0 \leqslant w, k \leqslant 10^9$