Trong một vùng sinh thái có ~n~ hòn đảo đánh số từ ~1~ đến ~n~. Ở ~k~ hòn đảo trong số này có các khu nhà dành cho khách du lịch. Các đảo được nối với nhau bởi đúng ~n - 1~ cây cầu sao cho mọi đảo đều đi đến được với nhau. Với mỗi cây cầu, đều xác định được thời gian để một chiếc ô tô tải đi hết của nó (từ đảo này sang đảo kia). Hàng ngày Nam phải chuyển thực phẩm đến ~k~ khu nhà nghỉ bằng cách từ đất liền cập bến một đảo nào đó, sau đó dùng xe tải xuất phát từ đảo này đi hết tất cả ~k~ hòn đảo có khu nhà nghỉ. Anh ta dừng lại tại hòn đảo cuối cùng trong số ~k~ hòn đảo có nhà nghỉ và từ đây đi tàu thủy về đất liền. Nam muốn xác định với mỗi hòn đảo dùng làm nơi xuất phát thì tổng quãng đường lái xe tải tối thiểu là bao nhiêu?

Dữ liệu:

• Dòng đầu tiên ghi hai số nguyên ~n,k~ (~1<n≤5~.~10^5~,~1<k<n~)</li>
• ~n-1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~A,B,C~ (~1≤A,B≤𝑁,1≤C≤10^6~) thể hiện có một cầu nối đảo ~A~ với đảo ~B~ có độ dài ~C~.
• ~k~ dòng cuối cùng, mỗi dòng ghi chỉ số của một hòn đảo có nhà nghỉ

Kết quả:

Gồm ~n~ dòng, dòng thứ ~i~ ghi quãng đường ngắn nhất mà Nam phải lái xe nếu như xuất phát từ đảo thứ ~i~.

Ví dụ:

Input

5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5

Output

5
3
7
2
2

Ràng buộc:

• Có 40% số test tương ứng 40% số điểm có ~𝑁≤1000~
• Có 20% số test tương ứng 20% số điểm có ~1000<𝑁~<~10^5~
• 40% số test còn lại tương ứng 40% số điểm có ~10^5~≤~𝑁<5~.~10^5~