JOI 王国有 $N$ 个车站，编号为 $1$ 到 $N$。JOI 王国共有 $M$ 条铁路线，编号为 $1$ 到 $M$。第 $i$ 条铁路线（$1 \le i \le M$）连接车站 $A_i$ 和车站 $B_i$，双向通行，通行时间为 $C_i$ 分钟。

作为 JOI 王国的大臣，你决定按如下方式修建一条新铁路线：

• 你选择两个整数 $u$ 和 $v$，满足 $1 \le u < v \le N$。你修建一条连接车站 $u$ 和车站 $v$ 的新铁路线，双向通行，通行时间为 $L$ 分钟。注意，你选择的两个整数之间可能已经存在一条连接车站 $u$ 和车站 $v$ 的铁路线。

修建新铁路线后，如果国王可以通过现有的铁路线在 $K$ 分钟内从车站 $S$ 到达车站 $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$

输出格式

将结果输出到标准输出。输出应包含能让国王感到高兴的选择 $u$ 和 $v$ 的方式总数。

数据范围

• $2 \le N \le 200\,000$
• $1 \le M \le 200\,000$
• $1 \le S < T \le N$
• $1 \le L \le 10^9$
• $1 \le K \le 10^{15}$
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$)
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \le i < j \le M$)
• $1 \le C_i \le 10^9$ ($1 \le i \le M$)
• 输入的所有值均为整数。

子任务

1. (8 分) $L = 1, K = 2, C_i = 1$ ($1 \le i \le M$)。
2. (16 分) $N \le 50, M \le 50$。
3. (29 分) $N \le 3\,000, M \le 3\,000$。
4. (47 分) 无附加限制。

样例

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

样例输出 1

4

样例输入 2

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

样例输出 2

3

样例输入 3

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

样例输出 3

0

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

样例输出 4

16