Giải bài trực tuyến

Thành phố nọ gồm N ngôi làng và các ngôi làng được nối với nhau dạng cây, nghĩa là có N – 1 nối một số ngôi làng với nhau sao cho giữa 2 ngôi làng bất kì đều có một đường đi qua các con đường giữa chúng. Có N thành viên của đội tình nguyện đang ở ngôi làng trung tâm của thành phố và họ đang rất mệt mỏi sau một ngày làm việc. Bạn là tài xế, và bạn đang muốn chở họ về nhà nhanh nhất có thể. Bạn sẽ chở tất cả mọi người ở trên xe, đi tới từng nhà của từng người một. Có K người trong đội tình nguyện, nhà của họ đều nằm trong các làng, và không có ai cùng làng cả. Khi chở người cuối cùng tới nhà, bạn sẽ ở lại đó luôn qua đêm.

            Tuy biết địa chỉ nhà của từng người, nhưng bạn phải quyết định xem thứ tự chở mọi người thế nào là nhanh nhất. Thêm vào đó, bạn không hề biết trung tâm thành phố ở đâu. Nhiệm vụ của bạn là với mỗi một thành phố, giả sử đó là trung tâm thành phố thì bạn cần ít nhất bao nhiêu thời gian để thực hiện lộ trình trên.

Input

• Dòng đầu là số N và K là số làng và số người cần về nhà (0 < N < 500.001, 1 ≤ K ≤ N)
• N – 1 dòng sau mỗi dòng ghi 3 số A, B, C, nghĩa là có đường nối giữa làng A và làng B với thời gian đi qua là C. (1 ≤ A, B ≤ N, 0 ≤ C ≤ 1.000.000)
• K dòng sau, dòng thứ i là làng mà người thứ i muốn về.

Output

Gồm N dòng, dòng thứ i là thời gian nhanh nhất của lộ trình nếu thành phố i là thành phố trung tâm.

Example

Input:
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5
Output:
5
3
7
2
2