题目描述

题目译自 JOI 2024 Final T2 「建設事業 2 / Construction Project 2」

JOI 国有 $N$ 个火车站，编号从 $1$ 到 $N$。另外，JOI 国有 $M$ 条双向铁路线，编号从 $1$ 到 $M$。铁路线 $i\ (1 \leq i \leq M)$ 连接了火车站 $A_{i}$ 和火车站 $B_{i}$，从一个站到另一个站需要花费 $C_i$ 分钟。

你是 JOI 国的部长，决定按照以下方式新建一条铁路线：

• 选择两个整数 $u, v\ (1 \leq u<v \leq N)$。在火车站 $u$ 和火车站 $v$ 之间建设一条双向铁路线，从一个站到另一个站需要花费 $L$ 分钟。注意，即使已经有一条连接火车站 $u$ 和火车站 $v$ 的铁路线也可以建设。

如果你建设这条铁路线后，可以花费不超过 $K$ 分钟从火车站 $S$ 到火车站 $T$，国王就会高兴。我们不考虑换乘时间和等待时间。

你有 $\frac{N(N-1)}{2}$ 种选择两个整数 $u, v$ 的方法，你想知道其中有多少种方法会让国王高兴。

给定火车站和铁路线以及国王的要求的信息，编写一个程序，求出其中有多少种选择整数的方法会让国王高兴。

输入格式

第一行包含两个整数 $N,M$。

第一行包含两个整数 $S,T,L,K$。

接下来 $M$ 行，每行包含三个整数 $A_i, B_i, C_i$，表示第 $i$ 条双向铁路线。

输出格式

输出一行一个整数，表示让国王高兴的两个整数的选择方法有多少种。

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

例如，你选择了 $u=3, v=6$。在火车站 $3$ 和火车站 $6$ 之间建设一条双向铁路线，需要 $1$ 分钟。

这时，可以按照以下方式，花费 $2$ 分钟从火车站 $6$ 到火车站 $7$。

1. 使用连接火车站 $3$ 和火车站 $6$ 的铁路线，花费 $1$ 分钟从火车站 $6$ 到火车站 $3$ 。
2. 使用连接火车站 $3$ 和火车站 $7$ 的铁路线，花费 $1$ 分钟从火车站 $3$ 到火车站 $7$。

让国王高兴的两个整数的选择方法有 $4$ 种。所以输出 $4$。

这个样例满足子任务 $1,2,3,4$ 的限制。

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

3

无论你选择哪两个整数，国王都会高兴。也就是说，让国王高兴的两个整数的选择方法有 $3$ 种。所以输出 $3$。

这个样例满足子任务 $1,2,3,4$ 的限制。

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

0

无论你选择哪两个整数，国王都不会高兴。所以输出 $0$。

这个样例满足子任务 $2,3,4$ 的限制。

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

这个样例满足子任务 $2,3,4$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $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)$

详细子任务附加限制及分值如下表所示。