Problem Description
There are N cities (numbered 0 to N-1) and R roads connecting them, with the ith road connecting cities Ai and Bi, and requires time Ti to traverse. There are also E expressways, connecting the capital of the country, city 0, with some other city, Ci, and this expressway requires Si time to traverse.
The mayor wishes to remove a subset of expressways such that the minimum time taken to travel from the capital to any other city remains the same. Find out what is the maximum number of expressways he can remove. It is guaranteed that it is possible to travel between any two cities using only normal roads.
Input
The first line of input will contain three integers, N, R and E.
The next R lines of input will contain three integers each, Ai, Bi and Ti.
The next E lines of input will contain two integers each, Ci and Si.
Output
The first and only line of output should contain a single integer, the maximum number of expressways the mayor can remove.
Limits
For all subtasks: 1 ≤ Ti, Si ≤ 109, 0 ≤ Ai, Bi, Ci < N.
Subtask 1 (37%): 1 ≤ N, R, E ≤ 1000.
Subtask 2 (25%): 1 ≤ N, E ≤ 300000, R = N - 1, Ai = i, Bi = i + 1.
Subtask 3 (38%): 1 ≤ N, R, E ≤ 300000.
Subtask 4 (0%): Sample Testcases.
Sample Input 1
4 3 3
0 1 5
1 2 4
2 3 1
2 8
3 9
1 7
Sample Output 1
2
Sample Input 2
5 6 4
0 2 5
0 4 2
2 1 3
1 0 4
1 3 3
2 3 5
2 6
3 7
4 1
1 5
Sample Output 2
3