시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.3 초 1024 MB616612.766%

문제

Orange the Cat found a tree (an undirected connected acyclic graph) with $N$ vertices numbered from $1$ to $N$. On each edge $i$ ($1 ≤ i < N$) connecting vertices $x_i$ and $y_i$ there are $c_i$ special cat treats.

Orange can choose exactly $K$ vertices, walk from the root of the tree to each of the chosen vertices along the paths from the root to the respective vertices and take all the cat treats along those paths. Of course, he can only take the treats on each edge once. Because Orange is a curious cat, he wants to know the maximum possible number of treats he could take by choosing the $K$ vertices optimally, if the root of the tree were vertex $i$, for each $i$ from $1$ to $N$.

입력

The first line of the input contains two integers $N$ and $K$, the number of vertices of the tree and the number of vertices Orange will choose, respectively. The next $N - 1$ lines contain three integers each, $x_i$, $y_i$ and $c_i$, describing the edges of the tree.

출력

On line $i$ for $1 ≤ i ≤ N$ output the maximum number of treats Orange could take if the root of the tree were vertex $i$.

제한

  • $1 ≤ K ≤ N ≤ 100\,000$
  • $0 ≤ c_i ≤ 1\,000\,000\,000$, for $1 ≤ i < N$

서브태스크

번호배점제한
18

$N ≤ 18$

211

$N ≤ 200$, $K ≤ 20$

317

$N ≤ 1\,000$, $K ≤ 100$

420

$N ≤ 2\,000$

512

$K = 1$

632

No further restrictions

예제 입력 1

11 3
1 2 5
2 3 3
2 6 5
3 4 4
3 5 2
1 7 6
7 8 4
7 9 5
1 10 1
10 11 1

예제 출력 1

28
28
28
32
30
32
28
32
32
29
30

힌트

If the root is vertex $1$, then Orange can choose vertices $4$, $6$ and $9$. The paths from the root to the chosen vertices are $1 − 2 − 3 − 4$, $1 − 2 − 6$, $1 − 7 − 9$ and the number of treats along those paths is $5 + 3 + 4 + 5 + 6 + 5 = 28$. Note that the treats on edge $1 − 2$ are only counted once.

채점 및 기타 정보

  • 예제는 채점하지 않는다.