题目描述

在繁华的商业王国中，$N$ 座城市被 $M$ 条商路巧妙地连接在一起，形成了一个错综复杂的无向图网络。每条商路是双向通行的，并且任意两座城市之间最多只有一条直接的商路。每条商路都有它的规则，其中最引人注目的就是穿过 商路，需要缴纳过路费。因此，商人们在选择商路时必须格外认真。

有一位名叫小蓝的商人，他对于商路的花费有着自己独到的见解。在小蓝眼中，一条路线包含一条或多条商路，但路线的成本并不是沿途累积的过路费总和，而是这条路线上最贵的那一次收费。这个标准简单而直接，让他能迅速评估出一条路线是否划算。

于是，他设立了一个目标，即找出所有城市对，这些城市之间的最低路线成本介于他心中预设的两个数 $L$ 和 $R$ 之间。他相信，这样的路线既不会太廉价，以至于路况糟糕；也不会过于昂贵，伤害他精打细算的荷包。

作为小蓝的助手，请你帮助小蓝统计出所有满足条件的城市对数量。

输入格式

输入的第一行包含四个整数 $N, M, L, R$，表示有 $N$ 座城市和 $M$ 条双向通行的商路，以及小蓝心中预设的最高过路费的下限 $L$ 和上限 $R$。

接下来 $M$ 行，每行包含三个整数 $u, v,w$，表示城市 $u$ 和城市 $v$ 之间有一条双向通行的商路，过路费为 $w$。保证每对城市之间最多只有一条直接的商路。

输出格式

输出一行包含一个整数，表示满足条件的城市对数量。

5 5 1 2
1 2 2
1 3 5
1 4 1
2 4 5
2 5 4

3

提示

对于 30% 的评测用例，$1 \le N \le 10^3,1 \le M \le \min(2 \times 10^3,\frac{N×(N−1)}{2}), 1 \le L \le R \le 10^5，1 \le u, v \le N, u \ne v,1 \le w \le 10^5$。

对于所有评测用例，$1 \le N \le 10^5,1 \le M \le \min(2 \times 10^5,\frac{N×(N−1)}{2}),1 \le L \le R \le 10^9,1 \le u, v \le N, u \ne v，1 \le w \le 10^9$。

样例解释

在样例中，满足条件的城市对有 $(1, 2),(1, 4),(2, 4)$。