Satisfactory Path Counting

Mr. Malnar plans to visit n cities, labeled 1 through n. The cities are connected by n-1 bidirectional roads forming a tree. Each road has a restaurant offering a limited maximum weight of lamb meat. When traveling from city x to city y, Malnar will follow the unique shortest path (i.e. the path with the smallest number of roads). Along this path, he will stop at exactly one restaurant – the one capable of providing the maximum available lamb meat (if there are several, he may choose any one of them) – and he will eat all the meat provided.

If a path of length l (i.e. including l roads) allows him to eat w kilograms of lamb meat, and if it holds that

then he calls the path satisfactory.

Determine the number of ordered pairs (x, y) (x and y are distinct cities) such that the unique shortest path from x to y is satisfactory.

inputFormat

The input is given as follows:

• The first line contains two integers n and k, where n is the number of cities and k is the parameter in the satisfaction condition.
• Each of the following n-1 lines contains three integers u, v, and m, indicating that there is a bidirectional road between cities u and v with a restaurant that can provide at most m kilograms of lamb meat.

Cities are numbered from 1 to n.

outputFormat

Output a single integer – the number of ordered pairs (x, y) (x ≠ y) such that the unique shortest path from x to y is satisfactory.

sample

3 0
1 2 1
2 3 2

6