 # Kpath

You are given a tree with N nodes and non-negative weight edges. The tree root is 1.
You need to compute the Kth smallest cost of a path from any node to any of its descendants.
If there are less than K such paths, print -1. If there are multiple paths with the same cost, they should all be counted separately.

### Input

The first line of input contains two space-separated integers: N and K.
The following N - 1 lines describe the tree. Each of these lines contains three space-separated integers: x, y and w, describing an edge of weight w between nodes x and y.

### Output

The output contains exactly one integer: the Kth smallest cost of path that links some node to one of its descendants.

### Constraints

• 1 ≤ N ≤ 105
• 1 ≤ K ≤ N * (N - 1) / 2
• 0 ≤ weight of any edge ≤ 104

### Sample

InputOutputExplanation
5 3
1 2 1
1 3 5
3 4 10
3 5 2
5The paths from 1 to its descendants are:
• 1 → 2 (cost = 1)
• 1 → 3 (cost = 5)
• 1 → 4 (cost = 5 + 10 = 15)
• 1 → 5 (cost = 5 + 2 = 7)
The paths from 3 to all its descendants are:
• 3 → 4 (cost = 10)
• 3 → 5 (cost = 2)
Note that the nodes {2, 4, 5} are leafs, so they do not have any descendants.
If we sort all the costs we get the following sequence:
• 1 2 5 7 10 15
So, the 3rd smallest value is 5. Questions?