Đất nước vui vẻ

Đất nước "vui vẻ" có \(n\) thành phố được đánh số từ \(1\) đến \(n\), và \(n − 1\) con đường hai chiều nối một số cắp thành phố. Giữa hai thành phố bất kỳ luôn có đường đi trực tiếp hoặc đường đi gián tiếp qua một số thành phố trung gian.

Có \(k\) thành phố nổi tiếng mà khách du lịch luôn muốn đến thăm. Khách du lịch sẽ bắt đầu từ một thành phố nào đó trong \(n\) thành phố, đi theo các con đường nối giữa các thành phố để thăm đủ k thành phố nổi tiếng (mỗi con đường/thành phố có thể đi qua nhiều lần). Đất nước khá là vui vẻ trừ giá taxi ở đây, nên khách du lịch muốn chọn
lộ trình có tổng độ dài phải đi là nhỏ nhất. Nhưng bạn biết đấy, sẽ thật phiền phức khi vừa đi du lịch vừa phải code, họ sẽ rất vui vẻ nếu nhận được sự giúp đỡ của bạn

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(k\)

• \(n − 1\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên dương \(u, v, L\); cho biết có một con đường độ dài \(L\) nối giữa hai thành phố \(u, v\)

• Dòng tiếp theo chứa \(k\) số nguyên dương là số hiệu của \(k\) thành phố nổi tiếng

Output

Gồm n dòng, dòng thứ \(i\) là tổng độ dài phải đi của lộ trình tốt nhất nếu khách du lịch bắt đầu từ thành phố \(i\)

Example

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

13
12
11
10
13
13
12
12
11
13
13
11
10

Scoring

• \(1 ≤ k ≤ n ≤ 10^5\)

• \(1 ≤ L ≤ 10^9\)

• Có \(50\%\) số test với \(n ≤ 1000\).