[AdditionalFile3225.zip](file://AdditionalFile3225.zip?type=additional_file)

#3225. 「PA 2019」Podatki drogowe

标签: 传统 | 时间限制: 7000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2019 Runda 5 Podatki drogowe

给定一棵 $n$ 个点的无根树，点的编号为 $1$ 到 $n$。第 $i$ 条边连接点 $a_i$ 和 $b_i$，边权为 $n^{p_i}$。

定义 $u$ 到 $v$ 的距离 $d(u, v)$ 为 $u$ 和 $v$ 在树上的简单路径的边权之和。

给定 $k$，请在 $\frac{n(n-1)}{2}$ 个 $d(u, v)$（$1 \le u < v \le n$）中找到第 $k$ 小的值。

输入格式

第一行两个正整数 $n, k$。

接下来 $n - 1$ 行，每行三个正整数 $a_i, b_i, p_i$，表示一条连接 $a_i$ 和 $b_i$ 的边，其边权为 $n^{p_i}$。

输出格式

输出一行一个整数，即第 $k$ 小的值对 $10^9+7$ 取模的结果。

样例

输入

5 8
1 2 1
3 1 3
3 4 1
5 3 2

输出

135

所有的 $d(u, v)$ 有：$5, 5, 25, 30, 125, 130, 130, 135, 150, 155$，第 $8$ 小的为 $135$，是 $u=2, v=4$ 这条路径。

数据范围与提示

$2 \le n \le 25000, 1 \le k \le \frac{n(n-1)}{2}, 1 \le a_i, b_i, p_i \le n$