Giving an undirected weighted graph of n (n <= 1e5) vertices , n — 1 edges and an positive integer k (k <= 1e9). Count the number of pairs (i , j) that i < j and the weight of the path from i to j is not bigger than k.

Input the first line contain n and k the following n — 1 lines each contains three positive integer u , v , w (u , v <= n , w <= 1e9)

Output the number of pairs (i , j) that the weight of the path from i to j is not bigger than k.

Sample

INPUT
6 8
1 2 2 
2 3 4
2 5 1
4 5 3
5 6 5

OUTPUT
14

Hi everyone, I've encountered a rather difficult problem for me, I hope you guys can give me some suggestions. The problem is as follows for a positive integer S (S <= 1e9), find how many ways to decompose the number S into the sum of positive integers whose greatest common divisor is 1.(Two sets of numbers that are vin permutations are also counted as different).

My solution is to count the divisors of (a*b)^2 but a, b <= 1e6. In addition the problem has testcase <= 1e6. Can you help me?