Bình là người phụ trách logistics cho hệ thống siêu thị gồm \(N\) kho trung chuyển. Có \(M\) tuyến đường liên kết hai chiều.

Có \(S\) kho trung chuyển lớn là các tổng kho phân phối. Hãy tìm khoảng cách ngắn nhất từ mỗi kho trung chuyển trong số \(N\) kho đến tổng kho phân phối gần nhất.

Định dạng đầu vào

• Dòng đầu chứa ba số nguyên \(N, M, S\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\), \(1 \le S \le N\)).
• Dòng thứ hai chứa \(S\) số nguyên là số hiệu của các tổng kho.
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N\), \(1 \le w \le 10^9\)) mô tả tuyến đường hai chiều nối \(u\) và \(v\) có độ dài \(w\).

Định dạng đầu ra

• Một dòng chứa \(N\) số nguyên, số thứ \(i\) là khoảng cách ngắn nhất từ kho \(i\) đến tổng kho gần nhất. Nếu kho \(i\) không thể kết nối đến bất kỳ tổng kho nào, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

4 4 2
1 4
1 2 2
2 3 3
3 4 4
1 3 8

Output:

0 2 4 0