P10206 [JOI 2024 Final] Construction Project 2 / Construction Project 2

JOI Country has $N$ train stations, numbered from $1$ to $N$. In addition, JOI Country has $M$ undirected railway lines, numbered from $1$ to $M$. Railway line $i\ (1 \leq i \leq M)$ connects station $A_i$ and station $B_i$, and it takes $C_i$ minutes to travel from one station to the other. You are the minister of JOI Country and decide to build a new railway line in the following way: Choose two integers $u, v\ (1 \leq u < v \leq N)$, and build an undirected railway line between station $u$ and station $v$. It takes $L$ minutes to travel from one station to the other. Note that you may build it even if there is already a railway line connecting station $u$ and station $v$. If, after building this railway line, it is possible to travel from station $S$ to station $T$ in at most $K$ minutes, the king will be happy. We do not consider transfer time or waiting time. There are $\frac{N(N-1)}{2}$ ways to choose the two integers $u, v$. You want to know how many of these ways will make the king happy. Given the information about the stations and railway lines, as well as the king’s requirement, write a program to compute how many ways of choosing the two integers will make the king happy.

The first line contains two integers $N, M$. The second line contains four integers $S, T, L, K$. Each of the next $M$ lines contains three integers $A_i, B_i, C_i$, representing the $i$-th undirected railway line.

Output one line containing one integer, the number of ways to choose the two integers that will make the king happy.

For all input data, the following constraints hold: - $2 \leq N \leq 2\times 10^5$. - $1 \leq M \leq 2\times 10^5$. - $1 \leq S < T \leq N$. - $1 \leq L \leq 10^{9}$. - $1 \leq K \leq 10^{15}$. - $1 \leq A_i < B_i \leq N\ (1 \leq i \leq M)$. - $(A_i, B_i) \neq (A_j, B_j)\ (1 \leq i < j \leq M)$. - $1 \leq C_i \leq 10^{9}\ (1 \leq i \leq M)$. The detailed additional constraints and scores for the subtasks are shown in the table below. |Subtask|Additional Constraints|Score| |:-:|:-:|:-:| |1|$L = 1, K = 2, C_i = 1\ (1 \leq i \leq M)$|8| |2|$N \leq 50, M \leq 50$|16| |3|$N \leq 3000, M \leq 3000$|29| |4|No additional constraints.|47| Translated by ChatGPT 5