Bệnh viện gần nhất

Một thành phố có $n$ nút giao thông đánh số từ $1$ đến $n$ và $m$ con đường một chiều; con đường thứ $i$ đi từ $u_i$ tới $v_i$ và dài $w_i$. Có thể có đường từ một nút về chính nó và nhiều đường giữa cùng một cặp nút.

Có $k$ nút đặt bệnh viện. Với mỗi nút $v$, hãy tìm độ dài đường đi ngắn nhất từ $v$ tới một bệnh viện (đi đúng chiều các con đường) và cho biết đó là bệnh viện nào. Nếu có nhiều bệnh viện cùng gần nhất, chọn bệnh viện đặt ở nút có số thứ tự nhỏ nhất. Nếu $v$ là bệnh viện thì khoảng cách bằng $0$ và bệnh viện là chính $v$.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n$, $m$, $k$.
• Dòng thứ hai chứa $k$ số nguyên khác nhau: các nút có bệnh viện.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,w_i$.

Dữ liệu ra

In ra $n$ dòng, dòng thứ $v$ gồm hai số: độ dài đường đi ngắn nhất từ $v$ tới bệnh viện gần nhất và nút đặt bệnh viện đó; hoặc $-1$ nếu từ $v$ không tới được bệnh viện nào.

Ràng buộc

• $1\le k\le n\le 5·{10}^4$
• $0\le m\le {10}^5$
• $1\le u_i,v_i\le n$
• $1\le w_i\le {10}^9$

Ví dụ