P17432 [LBA-OI R5 B] 彼方的她

:::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$， 表示一条无向边。

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

### 样例解释 - 样例 #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|无限制|