Description

Given an unrooted tree with $n$ nodes, numbered from $1$ to $n$. The weight of every edge is a positive integer power of $n$.

Define the distance $\operatorname{d(u,v)}$ from $u$ to $v$ as the sum of edge weights along the unique simple path between $u$ and $v$ in the tree.

Given $k$, among the $\dfrac{n\times (n-1)}{2}$ values $\operatorname{d(u,v)}(1\le u<v\le n)$, find the $k$-th smallest value.

Input Format

The first line contains two positive integers $n, k$.

The next $n-1$ lines each contain three positive integers $x, y, z(1\le x, y, z\le n)$, indicating an edge connecting $x$ and $y$ with weight $n^z$.

Output Format

Output one integer: the $k$-th smallest value modulo $10^9+7$.

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

135

Hint

For $100\%$ of the testdata, $2\le n\le 2.5\times 10^4$, and $1\le k\le \dfrac{n*(n-1)}{2}$.

Sample Explanation

After sorting all $d$, we get, in order: $5, 5, 25, 30, 125, 130, 130, 135, 150, 155$.

Translated by ChatGPT 5