Đóng tuyến đường sắt

Một đất nước có $n$ thành phố đánh số từ $1$ đến $n$, trong đó thành phố $1$ là thủ đô. Có $m$ con đường bộ hai chiều; con đường thứ $i$ nối hai thành phố $u_i$ và $v_i$ với độ dài $x_i$. Ngoài ra còn có $k$ tuyến đường sắt, tuyến thứ $i$ nối trực tiếp thủ đô với thành phố $s_i$ theo cả hai chiều và có độ dài $y_i$.

Chính phủ muốn đóng cửa càng nhiều tuyến đường sắt càng tốt để tiết kiệm chi phí, nhưng phải giữ nguyên khoảng cách ngắn nhất từ mọi thành phố về thủ đô. Hãy tính số tuyến đường sắt nhiều nhất có thể đóng.

Lưu ý rằng giữa hai thành phố có thể có nhiều con đường bộ, và cũng có thể có nhiều tuyến đường sắt cùng dẫn tới một thành phố.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i$, $v_i$, $x_i$ mô tả một con đường bộ.
• $k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $s_i$, $y_i$ mô tả một tuyến đường sắt.

Dữ liệu đảm bảo từ mọi thành phố đều có thể đi tới thủ đô.

Dữ liệu ra

Một số nguyên duy nhất: số tuyến đường sắt nhiều nhất có thể đóng.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le m\le 3·{10}^5$
• $1\le k\le {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$, $1\le x_i\le {10}^9$
• $2\le s_i\le n$, $1\le y_i\le {10}^9$

Ví dụ