Jzzhu là tổng thống của nước A. Có \(n\) thành phố được đánh số từ 1 đến \(n\) trong nước của ông ấy. Thành phố 1 là thủ đô của A. Ngoài ra, có \(m\) con đường kết nối các thành phố. Người ta có thể đi từ thành phố \(u_i\) đến \(v_i\) (và ngược lại) bằng con đường thứ \(i\), chiều dài của con đường này là \(x_i\). Đất nước A cũng có \(k\) tuyến đường sắt trong nước. Người ta có thể sử dụng tuyến đường sắt thứ \(i\) để đi từ thủ đô của nước đến thành phố \(s_i\) (và ngược lại), chiều dài của tuyến đường này là \(y_i\).

Jzzhu không muốn lãng phí tiền của đất nước, vì vậy ông ấy sẽ bỏ đi một số tuyến đường sắt. Hãy cho Jzzhu biết số lượng tối đa các tuyến đường sắt có thể bỏ với điều kiện sau: chiều dài của đường đi ngắn nhất từ mọi thành phố đến thủ đô không thay đổi.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(k\) (\(2 \leq n \leq 10^5\); \(1 \leq m \leq 3 \cdot 10^5\); \(1 \leq k \leq 10^5\)).

• Mỗi một trong \(m\) dòng tiếp theo chứa ba số nguyên \(u_i\), \(v_i\), \(x_i\) (\(1 \leq u_i, v_i \leq n\); \(u_i \neq v_i\); \(1 \leq x_i \leq 10^9\)).

• Mỗi một trong \(k\) dòng tiếp theo chứa hai số nguyên \(s_i\) và \(y_i\) (\(2 \leq s_i \leq n\); \(1 \leq y_i \leq 10^9\)).

• Đảm bảo rằng luôn có ít nhất một đường đi từ mọi thành phố đến thủ đô. Lưu ý rằng có thể có nhiều con đường giữa hai thành phố. Ngoài ra, có thể có nhiều tuyến đường sắt đến cùng một thành phố từ thủ đô.

Output

• Gồm một số nguyên là số tuyến đường sắt lớn nhất mà có thể bãi bỏ.

Example

5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5

2