시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 2 2 (100%) 2
문제
홍수가 난 어떤 마을에 초능력자를 위한 캠프가 열리고 있다. 마을은 $1$부터 $N$까지 차례대로 넘버링 된 $N$개의 집으로 이루어져 있고, 집 사이엔 $N-1$개의 도로가 있어, 두 마을 사이의 경로가 유일하도록 되어 있다. 각 도로에 대해 트럭이 그 도로를 통과하는데 얼마나 걸리는지 안다. 캠프는 어느 한 집의 뒷마당에서 열려야 하는데, 아직 어떤 집에서 열릴지 정해지지 않았다. 미르코는 운전자로 임명되었다. 그는 자원 봉사자들의 팀을 데리고 다니며 각 팀이 가야할 곳으로 운전한다. $K$개의 팀이 있으며, 모두 다른 집으로 가게 된다. 처음엔 $K$개의 팀 전부 미르코의 트럭에 오르며, 미르코는 본인이 정한 순서대로 팀을 내려준다. 마지막 팀을 내려준 뒤에는 본부로 돌아갈 필요 없이 그가 자원 봉사자들을 돕는다. 미르코는 각 집에 대해, 그 집이 본부일 때 모든 팀을 지정된 위치에 운전해주는데 걸리는 최소 시간을 구해야 한다. 미르코를 도와 이 문제를 해결할 프로그램을 작성하자.
입력
첫 줄에 $N (1 \le N \le 500,000)$과 $K (1 \le K \le N)$가 주어진다. 그 다음 $N-1$개의 각 줄엔 세 개의 정수 $A_i$, $B_i$, $C_i$ $(1 \le A_i, B_i \le N, 1 \le C_i \le 1,000,000)$가 주어지는데, 이는 $A_i$와 $B_i$ 마을을 잇는 도로는 지나가는데 $C_i$만큼의 시간이 걸린다는 것이다. 그 다음 $K$개의 줄엔 각각 $i$번째 줄이 어느 위치로 가는지 주어진다.
출력
$N$개의 줄을 출력한다. $i$번째 줄엔 본부가 집 $i$일 때 자원 봉사자들을 데려다 주는데 걸리는 최소 시간이 있어야 한다.
힌트
##### 입력 예제 ``` 5 2 2 5 1 2 4 1 1 2 2 1 3 2 4 5 ``` ##### 출력 예제 ``` 5 3 7 2 2 ``` ##### 입력 예제 ``` 7 2 1 2 4 1 3 1 2 5 1 2 4 2 4 7 3 4 6 2 3 7 ``` ##### 출력 예제 ``` 11 15 10 13 16 15 ```