#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

There are *N* cities (numbered 0 to *N*-1) and *R* roads connecting them, with the *i*th road connecting cities *A _{i}* and

*B*, and requires time

_{i}*T*to traverse. There are also

_{i}*E*expressways, connecting the capital of the country, city 0, with some other city,

*C*, and this expressway requires

_{i}*S*time to traverse.

_{i}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*and

_{i}*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^{9}, 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 37 | 22 | 1s | 256MB | Minimum |

2 | 25 | 21 | 1s | 256MB | Minimum |

3 | 38 | 62 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o expressways -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512