30078 - Tree

给出一棵有 n 个顶点的树,每条边都有长度(正整数,小于 1001)。

定义 \text{dist}(u, v) 为节点 uv 之间的最小距离。

给定整数 k,对于每对顶点 (u, v) 称为有效,当且仅当 \text{dist}(u, v) \le k

编写一个程序,计算给定树中有效对数。

输入

输入包含多个测试用例。每个测试用例的第一行包含两个整数 n, kn \le 10000)。

接下来的 n-1 行,每行包含三个整数 u, v, l,表示节点 uv 之间存在一条长度为 l 的边。

最后一个测试用例后面跟两个零。

输出

每个测试用例输出一行答案。

样例

输入

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

输出

8
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题