Problem Description

You are given a simple, connected, undirected weighted graph with $n$ vertices and $m$ edges. At time $0$, you are at vertex $1$.

Suppose the current time is $t$ and you are at vertex $v$. You may choose one of the following operations:

• Stay at vertex $v$. After the operation, the time becomes $t+1$.
• Choose an edge $(a,b,w)$ such that $a=v$ or $b=v$. Then you move to the other endpoint of this edge. After the operation, the time becomes $t+w$.

There are $k$ pieces of information. Each piece is of the form $(t_i,v_i)$, meaning that at time $t_i$, a flying pig with ID $i$ will appear at vertex $v_i$. If you are at $v_i$ at that time, then you capture flying pig $i$.

Now you need to find the maximum number of flying pigs you can capture.

Input Format

The first line contains three positive integers $n,m,k$.

The next $m$ lines each contain three positive integers $a_i,b_i,w_i$.

The next $k$ lines each contain two positive integers $t_i,v_i$.

Output Format

Output one integer in a single line: the maximum number of flying pigs you can capture.

2 1 5
1 2 2
1 2
2 2
3 2
5 1
7 2

4

Hint

Sample Explanation

The optimal plan is as follows:

At time $0$, choose to move to node $2$, and the time becomes $2$.
At time $2$, capture the $2$-nd flying pig, choose to stay at node $2$, and the time becomes $3$.
At time $3$, capture the $3$-rd flying pig, choose to move to node $1$, and the time becomes $5$.
At time $5$, capture the $4$-th flying pig, choose to move to node $2$, and the time becomes $7$.
At time $7$, capture the $5$-th flying pig.

Constraints

For $20\%$ of the testdata, $n,m,k\le 7$.
For $100\%$ of the testdata, $2\le n\le 200$, $1\le m\le \frac{n(n-1)}{2}$, $1\le k\le 5000$, $1\le a_i,b_i,v_i\le n$, $1\le w_i\le 1000$, $1\le t_i\le 10^9$.

Translated by ChatGPT 5