题目描述

题目译自 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

数据范围与提示

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