Một Trung tâm nghiên có ~n~ phòng thí nghiệm đặt ngầm trong lòng đất. Các phòng thí nghiệm được đánh số từ 1 đến ~n~ ~(1 ≤ n ≤ 10^5)~. Trung tâm có tất cả m đoạn đường hầm hai chiều nối trực tiếp hai phòng với nhau ~(1 ≤ m ≤ 10^5)~, sao cho từ một phòng bất kỳ có thể đi đến ~n-1~ phòng còn lại (có thể phải đi qua một số phòng trung gian). Không có đoạn đường hầm nào nối một phòng với chính nó, nhưng có thể có nhiều đoạn đường hầm cùng nối 2 phòng với nhau. Có ~k~ phòng có lối thoát hiểm lên trên mặt đất ~(1 ≤ k ≤ n)~. Trong trường hợp phải sơ tán khẩn cấp, tất cả các nhân viên phải tập trung ở những phòng có lối thoát hiểm lên trên mặt đất.

Yêu cầu: Hãy xác định quãng đường ngắn nhất để nhân viên mỗi phòng tập trung về phòng có lối thoát hiểm lên trên mặt đất trong trường hợp phải sơ tán khẩn cấp.

Dữ liệu vào:

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~k~.
• Dòng thứ 2 chứa k số nguyên khác nhau cho biết các phòng có cửa thoát hiểm.
• Dòng thứ 3 chứa số nguyên ~m~.
• Mỗi dòng trong m dòng tiếp theo chứa 3 số nguyên xác định cặp phòng có đoạn đường hầm nối trực tiếp và độ dài của đoạn đường hầm đó.

Dữ liệu ra:

• Ghi một dòng chứa ~n~ số nguyên, số thứ ~i~ xác định quãng đường ngắn nhất để nhân viên phòng ~i~ đi được tới phòng có lối thoát hiểm lên trên mặt đất. ~(1 ≤ i ≤ n)~.

Ví dụ:

Input

10 2
10 8 
10
6 7 1
7 5 1
5 8 1
8 1 1
1 10 1
10 3 1
3 4 1
4 9 1
9 2 1
3 9 1 

Output

1 3 1 2 1 3 2 0 2 0 

Ràng buộc:

• 30% số test có ~n≤10.000~ và ~k =1~.
• 30% số test có ~101≤n≤5000~.
• 40% số test có ~5000≤n≤100000~ và ~k ≤ 10~