Minimum Maximum Toll Path Count

In a bustling commercial kingdom, there are \(N\) cities connected by \(M\) bidirectional roads. Each road connects two distinct cities and has at most one direct road between any two cities. Each road charges a toll fee. A merchant, Xiao Lan, determines the cost of a path not by the sum of its tolls, but by the maximum toll fee encountered along that path.

For any pair of cities that are connected by one or more routes, the minimum route cost is defined as the minimum possible value of the maximum toll fee among all routes connecting them. Given two numbers \(L\) and \(R\), Xiao Lan wants to count how many unordered city pairs \((u,v)\) (with \(u < v\)) have the minimum route cost within the range \([L, R]\) inclusive.

Note: If two cities are not connected by any route, they are not counted.

inputFormat

The first line contains four integers \(N\), \(M\), \(L\), and \(R\) where \(N\) is the number of cities, \(M\) is the number of roads, and \(L\) and \(R\) define the toll cost range.

Each of the following \(M\) lines contains three integers \(u\), \(v\) and \(w\) representing a bidirectional road between city \(u\) and city \(v\) with a toll fee \(w\).

outputFormat

Output a single integer: the number of unordered pairs of cities whose minimum route cost lies in the range \([L, R]\) inclusive.

sample

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

6