P14633 [2018 KAIST RUN Fall] Utilitarianism

In RUN-land, there are $n$ cities numbered $1$ to $n$. Some pairs of cities are connected by a bidirectional road. It happens that there are $n-1$ roads in total and that for any two cities, there is a unique path from one to the other. Also, each road is assigned an integer called the $\textit{value}$. Today, to honor the $k$ co-founders of RUN-land, Alex, the king of RUN-land, has decided to choose $k$ different roads and give one road to each of the $k$ co-founders. To prevent unnecessary conflicts, there should be no city that is connected to more than one chosen roads. In this process, Alex, the king of RUN-land, does not care about who gets what road. Instead, Alex, the king of RUN-land, is only interested in the sum of the values of the $k$ chosen roads. Your task is to choose the roads to maximize this sum.

The first line contains two integers $n$ and $k$ ($2\leq n\leq250000$,$1\leq k\leq n-1$), which are 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$, $-10^6\leq c\leq 10^6$), which means that the city $u$ and the city $v$ are directly connected with a bidirectional road with value $c$.

If there is no way to choose $k$ roads to satisfy the conditions, print $\tt{Impossible}$. Otherwise, print one integer, the maximum sum of the values of the $k$ chosen roads.