Background

:::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.

Problem Description

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.

Input Format

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 Format

Output one integer, the answer.

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

Hint

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|<|<|A|$4$| |Subtask #2|^|<|<|B|$6$| |Subtask #3|$50$|$100$|$1000$|None|$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|No limit|<|<|^|$25$|

• Special Property A: For every undirected edge $(u, v, w)$, $w = 0$.
• Special Property B: $t = 0$.

This problem’s story is adapted from the visual novel game “Her Beyond”, everyone is welcome to try it.

The background image for this problem has a 6K resolution.

Translated by ChatGPT 5