Problem Description

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.

Input Format

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 Format

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

7 8
6 7 1 2
1 2 1
1 6 1
2 3 1
2 4 1
3 5 1
3 7 1
4 5 1
5 6 1

4

3 2
1 3 1 2
1 2 1
2 3 1

3

6 4
2 5 1000000000 1
1 2 1000000000
2 3 1000000000
2 4 1000000000
5 6 1000000000

0

18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645

16

Hint

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.

Translated by ChatGPT 5