Ở khu xóm "Tà tưa" có ~n~ ngôi nhà. Các ngôi nhà được kết nối với nhau bởi ~m~ con đường hai chiều có độ dài khác nhau. Từ một ngôi nhà bất kì, ta có thể đến được các ngôi nhà còn lại.

Người dân ở đây đều là những người nghiện trà sữa, do đó đã có ~k~ nhà tự mở quán trà sữa để phục vụ xóm làng. Họ muốn biết khoảng cách để tới quán trà sữa gần nhất. Với những ngôi nhà tự mở quán, có một vài người không muốn uống ở nhà nên sẽ tìm quán gần nhất khác quán của mình.

Yêu cầu: Với từng ngôi nhà, cho biết khoảng cách ngắn nhất để đi tới một quán trà sữa.

Input

Dữ liệu vào từ file văn bản milktea.inp

• Dòng đầu tiên gồm ba số nguyên ~n, m, k~ (~2 \le k \le n \le 10^5, n - 1 \le m \le min(\frac{n \times (n-1)}{2}, 2 \times 10^5~)) — lần lượt là số ngôi nhà, số con đường và số quán trà sữa.

• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u, v, w~ (~1 \le u, v \le n, 1 \le w \le 10^9~) — mô tả một con đường hai chiều nối hai ngôi nhà ~u~ và ~v~ với độ dài ~w~. Đầu vào đảm bảo không có con đường nào nối một ngôi nhà tới chính nó, cũng như không tồn tại hai con đường nối cùng một cặp ngôi nhà.

• ~k~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~p_i~ và ~t_i~ (~1 \le p_i \le n, t_i \in \{0, 1\}~) — mô tả quán trà sữa thứ ~i~. Nếu ~t_i = 1~ thì người ở nhà ~p_i~ cần tìm một quán trà sữa khác ~p_i~ để uống, ngược lại nếu ~t_i = 0~ thì có thể uống luôn tại nhà. Đầu vào đảm bảo các số ~p_i~ là phân biệt đôi một.

Output

Kết quả in ra file văn bản milktea.out

• Gồm một dòng chứa ~n~ số nguyên ~d_1, d_2, \dots, d_n~, với ~d_i~ là khoảng cách từ ngôi nhà thứ ~i~ đến quán trà sữa gần nhất.

Scoring

Sample Input 1

5 6 2
1 2 3
2 4 6
5 3 4
1 3 5
3 4 2
4 5 9
1 0
5 1

Sample Output 1

0 3 4 6 9

Notes

Trong ví dụ trên, có ~2~ quán trà sữa đặt tại các nhà ~1~ và ~5~. Người ở nhà ~1~ có thể uống trà sữa ngay tại nhà nên ~d_1 = 0~, còn người ở nhà ~5~ phải đi đến quán trà sữa ở nhà ~1~ theo con đường ~5 \rightarrow 3 \rightarrow 1~.