SOLVE
LATER
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.
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.
Print the $$k$$-th minimal mean weight as an irreducible fraction.
$$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
These are the vertical paths in the given tree: $$1 \rightarrow 2$$, $$1 \rightarrow 2 \rightarrow 3$$, $$1 \rightarrow 2 \rightarrow 4$$, $$1 \rightarrow 5$$, $$2 \rightarrow 3$$ and $$2 \rightarrow 4$$
Mean weights of the paths:
$$f(1 \rightarrow 2) = 2$$
$$f(1 \rightarrow 2 \rightarrow 3) = \frac{4}{2} = 2$$
$$f(1 \rightarrow 2 \rightarrow 4) = \frac{5}{2}$$
$$f(1 \rightarrow 5) = 2$$
$$f(2 \rightarrow 3) = 2$$
$$f(2 \rightarrow 4) = 3$$
So, if we sort these values, we get: $$2, 2, 2, 2, \frac{5}{2}, 3$$