Thị trấn Small đang bị
lụt nặng do vậy rất cần những tình nguyện viên giúp đỡ dân làng.
Trong thị trấn có N
ngôi nhà, các ngôi nhà được nối với nhau bằng N-1 tuyến đường 2 chiều,
giữa 2 ngôi nhà bất kỳ luôn có 1 đường đi trực tiếp hoặc gián tiếp qua các ngôi
nhà khác.
Chính quyền địa
phương đã chọn K ngôi nhà để dựng lều làm nơi tập trung dân làng.
John là một tình nguyện
viên và anh ta có một chiếc xe tải giúp vận chuyển lương thực đến K lều.
Trong lúc lũ lụt John cần tính toán làm thế nào để có thể chở lương thực đến tất
cả các lều trong thời gian nhanh nhất.
Hãy cho biết thời
gian ít nhất để John đến được K lều nếu John đang ở một ngôi nhà bất kỳ.
Dữ liệu vào: Từ tệp văn bản KAMP.INP
+ Dòng đầu tiên ghi 2
số nguyên dương N và K (1≤K≤N≤50000)
+ N-1
dòng tiếp theo, mỗi dòng 3 số nguyên u, v, c cho biết c là
thời gian để xe tải đi từ ngôi nhà u đến v. (1≤u, v≤N; 1≤c≤106)
+ Tiếp theo gồm k
dòng, mỗi dòng ghi 1 số nguyên là số hiệu của những ngôi nhà có lều trú cho người
dân.
Dữ liệu ra: ghi vào tệp văn bản KAMP.OUT
+ Gồm N
dòng, dòng thứ i cho biết thời gian ít nhất mà John lái xe chở lương thực đến K
lều nếu lúc đầu John đang ở ngôi nhà thứ i. Biết rằng John không phải quay về
điểm ban đầu sau khi đã đến tất cả K lều.
Ví dụ:
|
KAMP.INP
|
KAMP.OUT
|
|
KAMP.INP
|
KAMP.OUT
|
|
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
10
|
