Description

After you have successfully passed Huang Yaoshi (Huang Yaoshi)ʼs test, you can now freely tour Peach Blossom Island.

You start from the west end of the island and travel all the way to the east end, then leave from the pier at the east end. After one tour, you find the scenery of Peach Blossom Island so beautiful that you want to take a boat from the east pier back to the west end and tour again. However, there is a rule: you may tour any number of times, but the route taken each time cannot be exactly the same.

We model the island as a directed graph with $n$ vertices representing intersections and $m$ directed edges representing roads. Multiple edges between the same ordered pair of vertices may exist. The input guarantees that the graph has no cycles, and that there is at least one route from the west end to the east end. Two routes are considered different if and only if the exact sequence of edges they traverse is not identical.

Your task: How much total time does it take to finish touring all different routes? Between two consecutive tours, you take the boat from the east end back to the west end once, which costs $t_0$ time. After the last tour, you leave from the east pier and do not return.

Input Format

The first line contains $5$ integers $n, m, s, t, t_0$, representing the number of vertices, the number of edges, the index of the west end, the index of the east end (indices are from $1$ to $n$), and the time to take the boat once from the east end back to the west end.

Each of the following $m$ lines contains $3$ integers $x, y, t$, indicating that there is a directed edge from vertex $x$ to vertex $y$ with travel time $t$.

Numbers on each line are separated by a single space.

Output Format

Assume the total time is $total$. Output the value of $total \bmod 10000$ ($total$ modulo $10000$).

3 4 1 3 7
1 2 5
2 3 7
2 3 10
1 3 15

56

Hint

[Sample Explanation]

There are $3$ routes from vertex $1$ to vertex $3$, namely $1-2-3$, $1-2-3$, and $1-3$.

Time calculation: $(5+7)+7 + (5+10)+7 + (15) = 56$.

Constraints

$2 \le n \le 10^4$, $1 \le m \le 5 \times 10^4$, $t \le 10^4$, $t_0 \le 10^4$.

Translated by ChatGPT 5