P17432 [LBA-OI R5 B] Her Beyond

:::align{center} Her beyond, the flower on the other shore. :::  “The distance between us seems to be exactly 1000 light-years. So what I see is the Earth from 1000 years ago. This means that the sunlight shone on you after traveling for 8 minutes, then carried your appearance and traveled alone in the universe for 1000 years, and was finally caught by my eyes. It is very possible that I can see you at this very moment. Therefore, we may have met long ago. When we are both looking up at the starry sky, I might be gazing into your eyes.” — Aliya.

Aliya needs to return to Earth through a wormhole network. The wormhole network is an undirected graph with $n$ vertices and $m$ edges. Vertex $n$ is her starting point, and vertex $1$ is Earth. Each edge is of the form $(u, v, w)$, where $w$ is the “rollback time” of this wormhole tunnel, meaning it can go back to $w$ units of time earlier. She needs to go from $n$ to $1$, and: - She cannot traverse the same edge consecutively, i.e., $a \to b \to a$ cannot occur. - Vertex $1$ can only be the endpoint, and it must appear exactly once at the end of the path. - Other vertices may be visited multiple times. Let the total sum of edge weights along the path be $W$. Given a target time $t$, find $\min |W - t|$. The edge weight sum is defined as the total “rollback time” of all edges included in the path.

The first line contains three integers $n, m, t$.\ The next $m$ lines each contain three integers $u, v, w$, representing an undirected edge.

Output one integer, the answer.

### Sample Explanation - One valid path for Sample #1 is $4 \rightarrow 2 \rightarrow 3 \rightarrow 1$. - One valid path for Sample #2 is $5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1$. - The explanation for Sample #3 was lost by Aliya. ### Constraints For all testdata, it is guaranteed that $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$. Also, vertex $1$ and vertex $n$ are connected, and there are no multiple edges or self-loops. **This problem uses bundled subtasks.** ::cute-table{tuack} |Subtask ID|$n \le$|$m \le$|$t \le$|Special Property|Score| |:-:|:-:|:-:|:-:|:-:|:-:| |Subtask #1|No limit|