题目描述

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

JOI 国有 $N$ 个火车站，编号从 $1$ 到 $N$。另有 $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$ 分钟。允许在已有铁路线的站点间重复建设。

若建设该铁路线后，从火车站 $S$ 到火车站 $T$ 的最短时间不超过 $K$ 分钟，国王就会高兴。不考虑换乘时间和等待时间。

总共有 $\frac{N(N-1)}{2}$ 种选择 $u, v$ 的方法，请求出其中能让国王高兴的方法数。

输入格式

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

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

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

输出格式

输出一行一个整数，表示能让国王高兴的 $u, v$ 选择方法数。

样例 1

输入

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$ 新建铁路线（花费 $1$ 分钟）： 从 $6$ 到 $7$ 的最短路径为 $6 \to 3$（新建铁路，$1$ 分钟）$\to 7$（原有铁路，$1$ 分钟），总花费 $2$ 分钟，满足 $\leq K=2$。

能让国王高兴的选择方法共 $4$ 种，故输出 $4$。

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

样例 2

输入

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

输出

3

样例说明

无论选择哪对 $u, v$ 新建铁路线，$S=1$ 到 $T=3$ 的最短时间都不超过 $K=2$。总共有 $3$ 种选择方法，故输出 $3$。

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

样例 3

输入

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

输出

0

样例说明

无论选择哪对 $u, v$ 新建铁路线，$S=2$ 到 $T=5$ 的最短时间都超过 $K=1$，故输出 $0$。

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

样例 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

样例说明

能让国王高兴的选择方法共 $16$ 种，输出 $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$）

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

子任务	附加限制	分值
$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$	无附加限制	$47$