JOI 国有 $N$ 个火车站，编号为 $1$ 到 $N$。此外，JOI 国有 $M$ 条铁路线，编号为 $1$ 到 $M$。第 $i$ 条铁路线（$1 \leq i \leq M$）连接车站 $A_i$ 和车站 $B_i$（为双向通行），通过该线路需要 $C_i$ 分钟。

作为 JOI 国的大臣，你将新增 $1$ 条铁路线，其方式如下：

• 选择满足 $1 \leq u < v \leq N$ 的整数 $u, v$。修建一条连接车站 $u$ 和车站 $v$ 的双向铁路线，通过该线路需要 $L$ 分钟。注意，即使 $u$ 和 $v$ 之间已经存在铁路线，也可以再建。
• 修建完成后，如果可以从车站 $S$ 出发，经若干铁路线，在 $K$ 分钟以内到达车站 $T$，国王就会感到高兴。不考虑换乘时间和候车时间。

所有可能的整数对 $(u, v)$ 共有 $\frac{N (N-1)}{2}$ 种。你的任务是求出，在所有这些选择中，能够让国王感到高兴的 $(u, v)$ 的方案数。

给定火车站与铁路线、以及国王的期望，请编写程序，计算能让国王高兴的整数对有多少种。

输入通过标准输入给出，格式如下：

$N$ $M$ $S$ $T$ $L$ $K$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$

输出一行，表示能让国王高兴的整数对的方案数。

小子任务

1. （$8$ 分）$L = 1$，$K = 2$，$C_i = 1$（$1 \leq i \leq M$）。
2. （$16$ 分）$N \leq 50$，$M \leq 50$。
3. （$29$ 分）$N \leq 3000$，$M \leq 3000$。
4. （$47$ 分）无额外约束。

样例解释 1

比如选择 $u = 3, v = 6$，即修建一条连接车站 $3$ 和车站 $6$，耗时 $1$ 分钟的铁路线。

此时，可以从 $6$ 号站经这条新线路到 $3$ 号站，再从 $3$ 号站经已有铁路到 $7$ 号站，整个过程共需 $2$ 分钟。这样就能在 $2$ 分钟内到达 $7$ 号站，所以国王高兴。

国王高兴的整数对，包括上述情况，共有 $4$ 种。因此输出 $4$。

此输入满足小子任务 $1,2,3,4$ 的约束。

样例解释 2

不论选哪一组整数对，国王都高兴，因此方案数为 $3$，输出 $3$。

此输入满足小子任务 $1,2,3,4$ 的约束。

样例解释 3

不论选哪一组整数对，国王都不会高兴，因此输出 $0$。

此输入满足小子任务 $2,3,4$ 的约束。

样例解释 4

此输入满足小子任务 $2,3,4$ 的约束。

数据范围

• $2 \leq N \leq 200\,000$。
• $1 \leq M \leq 200\,000$。
• $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$）。
• 输入的所有数均为整数。

由 ChatGPT 5 翻译