Utilitarianism

Time limit5sMemory limit1024 MB

Summary

Pick k tree edges with no shared endpoints to maximize total value; the answer is a matching-style DP with a slope-trick lambda search over edge weights.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, Binary search, Greedy
Solved: No attempts yet

Problem

In RUN-land, there are $n$ cities numbered $1$ to $n$ . Some pairs of cities are connected by a bidirectional road. There are exactly $n-1$ roads, and between any two cities there is a unique path. Each road is assigned an integer called its value.

Today, to honor the $k$ co-founders of RUN-land, Alex, the king of RUN-land, will choose $k$ distinct roads and give one road to each of the $k$ co-founders. To avoid needless conflict, no city may be connected to more than one of the chosen roads.

Alex does not care who gets which road. He only cares about the sum of the values of the $k$ chosen roads. Choose the roads so that this sum is as large as possible.

Input

The first line contains two integers $n$ and $k$ ( $2\leq n\leq250,000$ , $1\leq k\leq n-1$ ), the number of cities in RUN-land and the number of roads to choose. Each of the next $n-1$ lines contains three integers $u,\ v,\ c$ ( $1\leq u,\ v\leq n$ , $-1,000,000\leq c\leq 1,000,000$ ), meaning that city $u$ and city $v$ are directly connected by a bidirectional road with value $c$ .

Output

If no choice of $k$ roads satisfies the conditions, print Impossible. Otherwise, print one integer, the maximum possible sum of the values of the $k$ chosen roads.

Examples3

Example 1
Input
```
5 1
1 2 2
2 3 3
2 4 10
4 5 6
```
Expected output
```
10
```
Example 2
Input
```
5 2
1 2 2
2 3 3
2 4 10
4 5 6
```
Expected output
```
9
```

Example 3

Input

Expected output

Impossible