Jzzhu is the president of country A. There are n cities numbered from 1 to n in his country. City 1 is the capital of A. Also there are m roads connecting the cities. One can go from city u_{i} to v_{i} (and vise versa) using the i-th road, the length of this road is x_{i}. Finally, there are k train routes in the country. One can use the i-th train route to go from capital of the country to city s_{i} (and vise versa), the length of this route is y_{i}.

Jzzhu doesn't want to waste the money of the country, so he is going to close some of the train routes. Please tell Jzzhu the maximum number of the train routes which can be closed under the following condition: the length of the shortest path from every city to the capital mustn't change.


-----Input-----

The first line contains three integers n, m, k (2 ≤ n ≤ 10^5; 1 ≤ m ≤ 3·10^5; 1 ≤ k ≤ 10^5).

Each of the next m lines contains three integers u_{i}, v_{i}, x_{i} (1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i}; 1 ≤ x_{i} ≤ 10^9).

Each of the next k lines contains two integers s_{i} and y_{i} (2 ≤ s_{i} ≤ n; 1 ≤ y_{i} ≤ 10^9).

It is guaranteed that there is at least one way from every city to the capital. Note, that there can be multiple roads between two cities. Also, there can be multiple routes going to the same city from the capital.


-----Output-----

Output a single integer representing the maximum number of the train routes which can be closed.


-----Examples-----
Input
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
2

Input
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3

Output
2

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '\n\n#===============================================================================================\n#importing some useful libraries.\n\n\n\nfrom fractions import Fraction\nimport sys\nimport os\nfrom io import BytesIO, IOBase\nfrom functools import cmp_to_key\n\n# from itertools import *\nfrom heapq import *\nfrom math import gcd, factorial,floor,ceil,sqrt\n\nfrom copy import deepcopy\nfrom collections import deque\n\n\nfrom bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom bisect import bisect\n\n#==============================================================================================\n#fast I/O region\nBUFSIZE = 8192\n\n\nclass FastIO(IOBase):\n    newlines = 0\n\n    def __init__(self, file):\n        self._fd = file.fileno()\n        self.buffer = BytesIO()\n        self.writable = "x" in file.mode or "r" not in file.mode\n        self.write = self.buffer.write if self.writable else None\n\n    def read(self):\n        while True:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            if not b:\n                break\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines = 0\n        return self.buffer.read()\n\n    def readline(self):\n        while self.newlines == 0:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            self.newlines = b.count(b"\\n") + (not b)\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines -= 1\n        return self.buffer.readline()\n\n    def flush(self):\n        if self.writable:\n            os.write(self._fd, self.buffer.getvalue())\n            self.buffer.truncate(0), self.buffer.seek(0)\n\n\nclass IOWrapper(IOBase):\n    def __init__(self, file):\n        self.buffer = FastIO(file)\n        self.flush = self.buffer.flush\n        self.writable = self.buffer.writable\n        self.write = lambda s: self.buffer.write(s.encode("ascii"))\n        self.read = lambda: self.buffer.read().decode("ascii")\n        self.readline = lambda: self.buffer.readline().decode("ascii")\n\n\ndef print(*args, **kwargs):\n    """Prints the values to a stream, or to sys.stdout by default."""\n    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)\n    at_start = True\n    for x in args:\n        if not at_start:\n            file.write(sep)\n        file.write(str(x))\n        at_start = False\n    file.write(kwargs.pop("end", "\\n"))\n    if kwargs.pop("flush", False):\n        file.flush()\n\n\nif sys.version_info[0] < 3:\n    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)\nelse:\n    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\n\n# inp = lambda: sys.stdin.readline().rstrip("\\r\\n")\n\n#===============================================================================================\n### START ITERATE RECURSION ###\nfrom types import GeneratorType\ndef iterative(f, stack=[]):\n  def wrapped_func(*args, **kwargs):\n    if stack: return f(*args, **kwargs)\n    to = f(*args, **kwargs)\n    while True:\n      if type(to) is GeneratorType:\n        stack.append(to)\n        to = next(to)\n        continue\n      stack.pop()\n      if not stack: break\n      to = stack[-1].send(to)\n    return to\n  return wrapped_func\n#### END ITERATE RECURSION ####\n\n#===============================================================================================\n#some shortcuts\n\ndef inp(): return sys.stdin.readline().rstrip("\\r\\n") #for fast input\ndef out(var): sys.stdout.write(str(var))  #for fast output, always take string\ndef lis(): return list(map(int, inp().split()))\ndef stringlis(): return list(map(str, inp().split()))\ndef sep(): return list(map(int, inp().split()))\ndef strsep(): return list(map(str, inp().split()))\n# def graph(vertex): return [[] for i in range(0,vertex+1)]\ndef zerolist(n): return [0]*n\ndef nextline(): out("\\n")  #as stdout.write always print sring.\ndef testcase(t):\n    for pp in range(t):\n        solve(pp)\ndef printlist(a) :\n    for p in range(0,len(a)):\n        out(str(a[p]) + \' \')\ndef google(p):\n    print(\'Case #\'+str(p)+\': \',end=\'\')\ndef lcm(a,b): return (a*b)//gcd(a,b)\ndef power(x, y, p) :\n    y%=(p-1)  #not so sure about this. used when y>p-1. if p is prime.\n    res = 1     # Initialize result\n    x = x % p  # Update x if it is more , than or equal to p\n    if (x == 0) :\n        return 0\n    while (y > 0) :\n        if ((y & 1) == 1) : # If y is odd, multiply, x with result\n            res = (res * x) % p\n\n        y = y >> 1      # y = y/2\n        x = (x * x) % p\n    return res\ndef ncr(n,r): return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))\ndef isPrime(n) :\n    if (n <= 1) : return False\n    if (n <= 3) : return True\n    if (n % 2 == 0 or n % 3 == 0) : return False\n    i = 5\n    while(i * i <= n) :\n        if (n % i == 0 or n % (i + 2) == 0) :\n            return False\n        i = i + 6\n    return True\ninf = pow(10,20)\nmod = 10**9+7\n#===============================================================================================\n# code here ;))\ndef djkistra(g,st,dist,lol,vis): #g contains b,dist(a to b) and dist is initiaalised by 10**9 initiallly\n    pq = []\n    dist[st] = 0\n    heappush(pq,(0,st))\n    while(len(pq) != 0):\n        curr = heappop(pq)[1]\n        for i in range(0,len(g[curr])):\n            b = g[curr][i][0]\n            w = g[curr][i][1]\n            if(dist[b] > dist[curr] + w):\n                dist[b] = dist[curr]+w\n                heappush(pq,(dist[b],b))\n\n\ndef modif_djkistra(g,dist,usedtrains):\n    h = []\n    for i in range(len(g)):\n        if(dist[i] != inf):\n            heappush(h,(dist[i],i))\n    while(len(h) != 0):\n        d,curr = heappop(h)\n        if(d != dist[curr]): #dublicate train with larger length\n            continue\n        for to,newd in g[curr]:\n            if(newd+d<=dist[to]):\n                usedtrains[to] = False\n                if(dist[to] > newd+d):\n                    heappush(h,(newd+d,to))\n                dist[to] = newd+d\n\ndef solve(case):\n    n,m,k = sep()\n    dist = [inf]*n;dist[0] = 0\n    g = [[] for i in range(n)]\n    for i in range(m):\n        a,b,c = sep()\n        a-=1\n        b-=1\n        g[a].append((b,c))\n        g[b].append((a,c))\n    have = []\n    usedtrain = [False]*n\n    for i in range(k):\n        a,b = sep()\n        a-=1\n        dist[a] = min(dist[a],b)\n        # g[0].append((a,b))\n        # g[a].append((0,b))\n        have.append(a)\n        usedtrain[a] = True\n    modif_djkistra(g,dist,usedtrain)\n    cnt = 0\n    have = list(set(have))\n    for i in range(n):\n        if(usedtrain[i]):\n            cnt+=1\n    # print(cnt)\n    print(k - cnt)\n\n\n\n\n\n\ntestcase(1)\n# testcase(int(inp()))\n\n\n\n\n\n\n\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 195530