Problem Description

In a prosperous commercial kingdom, $N$ cities are connected by $M$ trade roads, forming a complex undirected graph. Each road can be traveled in both directions, and there is at most one direct road between any two cities. Each road has its own rule: to pass through it, a toll must be paid. Therefore, merchants must be very careful when choosing roads.

There is a merchant named Xiaolan who has his own unique view on route costs. In Xiaolan’s eyes, a route consists of one or more roads, but the cost of the route is not the sum of all tolls along the way. Instead, it is the most expensive single toll on that route. This simple and direct standard allows him to quickly judge whether a route is worthwhile.

So, he sets a goal: find all pairs of cities such that the minimum possible route cost between them is between two preset numbers $L$ and $R$. He believes such routes will not be too cheap (and thus have poor conditions), nor too expensive (hurting his carefully planned budget).

As Xiaolan’s assistant, please help him count how many city pairs satisfy the condition.

Input Format

The first line contains four integers $N, M, L, R$, meaning there are $N$ cities and $M$ bidirectional trade roads, and the lower bound $L$ and upper bound $R$ of the preset maximum toll in Xiaolan’s mind.

The next $M$ lines each contain three integers $u, v, w$, meaning there is a bidirectional trade road between city $u$ and city $v$ with toll $w$. It is guaranteed that there is at most one direct road between any pair of cities.

Output Format

Output one line containing one integer, which is the number of city pairs that satisfy the condition.

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

3

Hint

For $30\%$ of the testdata, $1 \le N \le 10^3$, $1 \le M \le \min(2 \times 10^3, \frac{N \times (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$.

For all testdata, $1 \le N \le 10^5$, $1 \le M \le \min(2 \times 10^5, \frac{N \times (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$.

Sample Explanation

In the sample, the city pairs that satisfy the condition are $(1, 2)$, $(1, 4)$, and $(2, 4)$.

Translated by ChatGPT 5