#3225. 「PA 2019」Podatki drogowe

内存限制:1024 MiB 时间限制:7000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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