Hạo là tổng thống của đất nước \(A\). Trong đất nước \(A\) có \(n\) thành phố được đánh số từ \(1\) đến \(n\). Thành phố \(1\) là thủ đô của đất nước \(A\). Có \(m\) con đường hai chiều kết nối các thành phố lại với nhau. Và có \(k\) tuyến tàu, tuyến tàu thứ \(i\) là kết nối thủ đô đến thành phố \(s_i\) (và ngược lại) với độ dài là \(y_i\)

Hạo không muốn lãng phí tiền của đất nước, vì vậy Hạo quyết định đóng một số tuyến tàu không cần thiết. Hãy giúp Hạo xem có thể đóng tối đa bao nhiêu tuyến tàu mà vẫn giữa được đường đi ngắn nhất từ thủ đô đến mỗi thành phố khác.

Dữ liệu vào

• Dòng \(1\): \(3\) số nguyên \(n,m,k\) \((2 \le n \le 10^5; 1 \le m \le 3 \times 10^5; 1 \le k \le 10^5)\)
• \(m\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(u_i, v_i, x_i\) \((1 \le u_i, v_i \le n; u_i \neq v_i; 1 \le x_i \le 10^9)\)
• \(k\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên \(s_i\) và \(y_i\) \((2 \le s_i \le n; 1 \le y_i \le 10^9)\)
• Lưu ý: Dữ liệu đảm bảo có ít nhất \(1\) đường đi từ các thành phố đến thủ đô. Giữa hai thành phố có thể có nhiều đường đi.

Dữ liệu ra

• Số tuyến tàu nhiều nhất mà có thể đóng.

Input 1

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

Output 1

2

Input 2

2 2 3
1 2 2
2 1 3
2 1
2 2
2 3

Output 2

2