공리주의

RUN 나라에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 도시가 있다. 일부 도시 쌍은 양방향 도로로 연결되어 있다. 도로는 모두 $n-1$개이고, 임의의 두 도시 사이에는 유일한 경로가 존재한다. 또한 각 도로에는 가치라는 정수가 부여되어 있다.

오늘 RUN 나라의 공동 창립자 $k$명을 기리기 위해, RUN 나라의 왕 Alex는 서로 다른 도로 $k$개를 골라 창립자 한 명에게 도로 하나씩 나눠 주려고 한다. 불필요한 분쟁을 막기 위해, 고른 도로 두 개 이상과 연결된 도시가 있어서는 안 된다.

Alex는 누가 어느 도로를 받는지는 신경 쓰지 않는다. 대신 고른 도로 $k$개의 가치 합에만 관심이 있다. 이 합을 최대로 만드는 도로를 골라야 한다.

첫째 줄에 두 정수 $n$과 $k$가 주어진다($2\leq n\leq250,000$, $1\leq k\leq n-1$). $n$은 RUN 나라의 도시 수, $k$는 고를 도로의 수이다. 다음 $n-1$개 줄에 각각 세 정수 $u,\ v,\ c$가 주어진다($1\leq u,\ v\leq n$, $-1,000,000\leq c\leq 1,000,000$). 이는 도시 $u$와 도시 $v$가 가치 $c$인 양방향 도로로 직접 연결되어 있다는 뜻이다.

조건을 만족하도록 도로 $k$개를 고를 수 없으면 Impossible을 출력한다. 그렇지 않으면 고른 도로 $k$개의 가치 합의 최댓값을 정수 하나로 출력한다.