K-th Smallest Pair Distance in a Tree

Given an unrooted tree with n nodes numbered from 1 to n. The tree consists of n-1 edges and each edge has a weight that is a positive integer power of n (i.e. an edge weight can be written as \(n^p\) where \(p\) is a positive integer). The distance \(d(u,v)\) between two nodes \(u\) and \(v\) is defined as the sum of the weights of the edges on the unique simple path connecting them.

There are \(\frac{n\times (n-1)}{2}\) distances for all pairs \((u,v)\) with \(1 \le u < v \le n\). Given an integer k, your task is to find the k-th smallest distance among these distances.

inputFormat

The first line contains two integers n and k.

Each of the following n-1 lines contains three integers u, v and w, representing an edge between nodes u and v with weight w. It is guaranteed that each w is a positive integer power of n (i.e. \(w=n^p\) for some positive integer \(p\)).

outputFormat

Output a single integer — the k-th smallest distance among all pairs \((u, v)\) with \(1 \le u < v \le n\).

sample

3 2
1 2 3
2 3 9

9