Given a weighted rooted tree with n vertices. Let's call simple path from u to v vertical iff \(u \ne v\) and u is on simple path from root to v. The weight of the path is a sum of weights for all edges in the path. The mean weight of the path is a weight of the path divided by number of edges in it. Calculate mean weight of each vertical path, sort them and print k-th value in sorted order.

Input Format

The first line of input contains two integers n and k (\(2 \le n \le 10^{6}\)). It is guaranteed that there are at least k vertical paths in the given tree.

Next \(n-1\) lines contain description of edges \(u, v, c\) (\(1 \le u, v \le n, 1 \le c \le 10^{5}\)).

The root of the tree is vertex 1.

Output Format

Print the k-th minimal mean weight as an irreducible fraction.

Scoring

\(n \le 100~-\) 10 points

\(n \le 2000~-\) 10 points

\(n \le 15000\), \(k \le 10^{5}~-\) 15 points

\(n \le 15000~-\) 10 points

\(n \le 10^{5}~-\) 25 points

\(n \le 10^{6}, k \le 500~-\) 30 points