expressways

Problem Description

There are N cities (numbered 0 to N-1) and R roads connecting them, with the ith road connecting cities A_i and B_i, and requires time T_i to traverse. There are also E expressways, connecting the capital of the country, city 0, with some other city, C_i, and this expressway requires S_i 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, A_i, B_i and T_i.

The next E lines of input will contain two integers each, C_i and S_i.

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 ≤ T_i, S_i ≤ 10⁹, 0 ≤ A_i, B_i, C_i < N.

Subtask 1 (37%): 1 ≤ N, R, E ≤ 1000.

Subtask 2 (25%): 1 ≤ N, E ≤ 300000, R = N - 1, A_i = i, B_i = 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