题目背景

建议 Python 用户选择 PyPy3 提交本题。

题目描述

边境森林中分布着若干重要的哨站，所有哨站之间由隐秘小径相连，形成一张天然的巡逻网络。这张网络的结构恰好是一棵树。为了防止敌人渗透，小蓝每天需要执行固定长度为 $k$ 的巡逻任务。每次巡逻从一个哨站出发，经过不重复地恰好 $k$ 条道路，最终到达另一个哨站。每条道路都有一定的危险值，巡逻路径上危险值的和代表该次巡逻时的风险。两次巡逻路径不相同当且仅当它们的起点不同或终点不同。

现在指挥官希望知道，所有可能的长度为 $k$ 的巡逻路线的风险之和是多少？

输入格式

输入的第一行包含两个正整数 $n, k$ ，用一个空格分隔。

接下来 $n-1$ 行，每行包含三个正整数 $u_i, v_i, w_i$ ，相邻整数之间使用一个空格分隔。表示结点 $u_i$ 和结点 $v_i$ 之间有一条危险值为 $w_i$ 边。

输出格式

输出一行包含一个整数表示答案。

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

104

提示

【样例说明】

所有可能的路径及其风险值如下：

• $1 \rightarrow 2 \rightarrow 4: 8$
• $2 \rightarrow 1 \rightarrow 3: 10$
• $1 \rightarrow 3 \rightarrow 5: 10$
• $1 \rightarrow 3 \rightarrow 6: 11$
• $5 \rightarrow 3 \rightarrow 6: 7$
• $3 \rightarrow 6 \rightarrow 7: 6$

以上路径反过来也是合法的，所以总共有 14 条不同的路径，风险之和为 104。

【评测用例规模与约定】

对于 40% 的评测用例，$1 \leq n \leq 500$；

对于所有评测用例，$1 \leq n \leq 5000$，$1 \leq k \leq n$，$1 \leq u_i, v_i \leq n$，$1 \leq w_i \leq 10^6$。