题目描述

塔尖 国有 $n$ 个火车站，编号从 $1$ 到 $n$。另外，塔尖 国有 $m$ 条双向铁路线，编号从 $1$ 到 $m$。铁路线 $i\ (1 \leq i \leq m)$ 连接了火车站 $a_{i}$ 和火车站 $b_{i}$，从一个站到另一个站需要花费 $c_i$ 分钟。

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

选择两个整数 $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

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

提示

对于 $100\%$ 的数据数据，满足：$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}$。

• 给定的图无重边，且边权不超过 $10^9$。