题目描述

给你一棵大小为 $n$ 的树。树上节点编号从 $1$ 到 $n$。

有 $n-1$ 条边，其中第 $i$ 条边连接节点 $u_i$ 和 $v_i$，长度为 $1$，权值为 $w_i$。

我们定义树上一条以节点 $u$ 和 $v$ 为端点的节点路径的长度为路径上所有边的长度之和（即：边的数量），路径的权值为路径上所有边的权值之和。

求：树上所有长度恰好为 $k$ 的简单路径的权值总和。

输入格式

第一行，两个整数 $n$ 和 $k$。

接下来 $n-1$ 行，每行包含三个整数 $u_i, v_i, w_i$。

输出格式

输出一个整数，表示树上所有长度恰好为 $k$ 的路径的权值总和。

样例

7 2
1 2 3
2 4 5
1 3 7
3 5 3
3 6 4
6 7 2

52

说明/提示

数据规模与约定

• 对于 $40\%$ 的数据，$n \le 500$，$w_i \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 5000$，$1 \le k \le n$，$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^6$

数据保证这是一棵树。