背景

:::align{center} 彼方的她，彼岸之花 :::

“我们之间相隔的距离好像刚好是 1000 光年。所以我看到的是 1000 年前的地球。这意味着，太阳的光经过 8 分钟后照在了你的身上，然后又带着你的模样，在宇宙中孤独旅行了 1000 年最后被我的眼睛捕捉到。我现在很有可能能看到当下的你哦。因此，我们可能很早就认识，当我们都在仰望星空的时候，我可能正在注视着你的眼睛。”——Aliya

题目描述

Aliya 需要通过虫洞网络回到地球。虫洞网络是一张 $n$ 个点、$m$ 条边的无向图，第 $n$ 号点是她的起点，第 $1$ 号点是地球。每条边形如 $(u,v,w)$，其中 $w$ 为该虫洞隧道的“回溯时间”，表示可以回到 $w$ 个单位时间之前。

她要从 $n$ 走到 $1$，并且：

• 不能连续经过同一条边，即不能出现 $a \to b \to a$；
• 节点 $1$ 只能作为终点，且恰好在路径末尾出现一次；
• 其它节点可以重复经过。

设路径总边权和为 $W$，给定目标时间 $t$，求 $\min |W-t|$。

边权和定义为路径包含的边的“回溯时间”总和。

输入格式

第一行三个整数 $n, m, t$。
接下来 $m$ 行，每行三个整数 $u, v, w$， 表示一条无向边。

输出格式

输出一个整数，表示答案。

4 6 10
1 4 4
2 3 1
1 3 6
2 4 3
3 4 2
1 2 5

0

5 7 13
2 3 3
1 2 1
3 4 1
2 4 2
4 5 3
1 3 2
3 5 2

1

1 0 1

1

提示

样例解释

• 样例 #1 的一条合法路径为 $4 \rightarrow 2 \rightarrow 3 \rightarrow 1$；
• 样例 #2 的一条合法路径为 $5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1$；
• 样例 #3 的解释被 Aliya 弄丢啦。

数据范围

对于所有的测试数据，保证 $1 \le n \le 2 \times 10^5$，$0 \le m \le 2 \times 10^5$，$0 \le t \le 1000$，$0 \le mt \le 7 \times 10^6$，$0 \le w \le 10^6$，且 $1$ 号点和 $n$ 号点连通、不存在重边和自环。

本题目采用子任务捆绑测试。

::cute-table{tuack} |子任务编号|$n \le$|$m \le$|$t \le$|特殊性质|分值| |:-:|:-:|:-:|:-:|:-:|:-:| |Subtask #1|无限制|<|<|A|$4$| |Subtask #2|^|<|<|B|$6$| |Subtask #3|$50$|$100$|$1000$|无|$10$|  |Subtask #4|$200$|$1000$|$300$|^|^| |Subtask #5|$500$|$8000$|$100$|^|^| |Subtask #6|$6 \times 10^4$|<|$80$|^|$15$| |Subtask #7|$10^5$|<|$50$|^|$20$| |Subtask #8|无限制|<|<|^|$25$|

• 特殊性质 A：对于所有的无向边 $(u, v, w)$，均有 $w = 0$；
• 特殊性质 B：$t = 0$。

本题目故事改编自视觉小说游戏《彼方的她》，欢迎各位前来游玩。

题目背景图片的分辨率可是 6K 的哦。