Description

Mr. Malnar will visit $n$ cities, labeled with integers $1$ to $n$. He also found that there are $n-1$ bidirectional roads, each connecting two of the cities.

On each road there is a restaurant that serves lamb, and for each restaurant we are given the maximum weight of lamb that can be ordered.

He will choose two cities $x$ and $y$, and travel from $x$ to $y$ along a shortest path (i.e., a path that uses the fewest roads). He will stop at exactly one restaurant, namely the one that can provide the largest amount of lamb (if there are multiple such restaurants, he may choose any one), and he will eat all the lamb he orders.

If along a path of length $l$ he can eat $w$ kilograms of lamb, and $w-l \ge k$, then Mr. Malnar calls it satisfying. The length of a path is equal to the number of roads it uses.

Find how many ordered pairs $(x,y)$ make the shortest path from $x$ to $y$ satisfying.

Input Format

The first line contains integers $n,k$, where $n$ is the number of cities.

The next $n-1$ lines each contain three integers $x,y,w$, meaning there is a road connecting cities $x$ and $y$, and on that road there is a restaurant that provides $w$ kilograms of lamb.

Output Format

Output the number of ordered pairs that satisfy the requirement.

3 1
1 2 3
1 3 2

6

4 1
1 2 1
2 3 2
3 4 3

6

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

8

Hint

Sample 1 Explanation

The ordered pairs that satisfy the requirement are $(1,3),(3,1),(1,5),(5,1),(3,5),(5,3),(4,5),(5,4)$.

Constraints

This problem uses bundled evaluation.

For all testdata, $1 \le n,k,w \le 10^5$, $1 \le x,y \le n$, $x \neq y$.

Notes

The score setting follows the original COCI problem, with a full score of $110$.

Translated from COCI2020-2021 CONTEST #4 T4 Janjetina.

Translated by ChatGPT 5