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

Source: codeforces | Difficulty: HARD
Tags: Greedy algorithms

Graph algorithms

Shortest paths


Solutions:
import sys
input = sys.stdin.readline
import heapq
(n, m, k) = map(int, input().split())
adj = [[] for _ in range(n + 5)]
for _ in range(m):
	(u, v, w) = map(int, input().split())
	adj[u].append((v, w))
	adj[v].append((u, w))
train = [-1 for _ in range(n + 5)]
ans = 0
dist = [int(1000000000000000.0) for _ in range(n + 5)]
pq = []
for _ in range(k):
	(s, y) = map(int, input().split())
	if train[s] != -1:
		ans += 1
		train[s] = min(train[s], y)
		dist[s] = train[s]
		continue
	train[s] = y
	dist[s] = y
for i in range(n + 5):
	if dist[i] != -1:
		heapq.heappush(pq, (dist[i], i))
heapq.heappush(pq, (0, 1))
dist[1] = 0
cut = [0 for _ in range(n + 5)]
vis = [0 for _ in range(n + 5)]
while pq:
	(dummy, u) = heapq.heappop(pq)
	if vis[u]:
		continue
	vis[u] = 1
	for (v, w) in adj[u]:
		if dist[v] >= dist[u] + w:
			if dist[v] != dist[u] + w:
				heapq.heappush(pq, (dist[u] + w, v))
			dist[v] = dist[u] + w
			if train[v] != -1:
				cut[v] = 1
for b in cut:
	if b == 1:
		ans += 1
print(ans)


from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return list(map(int, inp().split()))

def strsep():
	return list(map(str, inp().split()))

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def djkistra(g, st, dist, lol, vis):
	pq = []
	dist[st] = 0
	heappush(pq, (0, st))
	while len(pq) != 0:
		curr = heappop(pq)[1]
		for i in range(0, len(g[curr])):
			b = g[curr][i][0]
			w = g[curr][i][1]
			if dist[b] > dist[curr] + w:
				dist[b] = dist[curr] + w
				heappush(pq, (dist[b], b))

def modif_djkistra(g, dist, usedtrains):
	h = []
	for i in range(len(g)):
		if dist[i] != inf:
			heappush(h, (dist[i], i))
	while len(h) != 0:
		(d, curr) = heappop(h)
		if d != dist[curr]:
			continue
		for (to, newd) in g[curr]:
			if newd + d <= dist[to]:
				usedtrains[to] = False
				if dist[to] > newd + d:
					heappush(h, (newd + d, to))
				dist[to] = newd + d

def solve(case):
	(n, m, k) = sep()
	dist = [inf] * n
	dist[0] = 0
	g = [[] for i in range(n)]
	for i in range(m):
		(a, b, c) = sep()
		a -= 1
		b -= 1
		g[a].append((b, c))
		g[b].append((a, c))
	have = []
	usedtrain = [False] * n
	for i in range(k):
		(a, b) = sep()
		a -= 1
		dist[a] = min(dist[a], b)
		have.append(a)
		usedtrain[a] = True
	modif_djkistra(g, dist, usedtrain)
	cnt = 0
	have = list(set(have))
	for i in range(n):
		if usedtrain[i]:
			cnt += 1
	print(k - cnt)
testcase(1)


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'
import heapq

def solve():
	(n, m, k) = map(int, input().split())
	adj_list = {x: [] for x in range(n + 1)}
	dist = [float('inf')] * (n + 1)
	dist[1] = 0
	hq = [(0, 1)]
	for _ in range(m):
		(u, v, x) = map(int, input().split())
		adj_list[u].append((v, x, False))
		adj_list[v].append((u, x, False))
	for _ in range(k):
		(v, y) = map(int, input().split())
		adj_list[1].append((v, y, True))
		adj_list[v].append((1, y, True))
	visited = [False] * (n + 1)
	prev = {}
	train_used = [0] * (n + 1)
	while hq:
		(d, node) = heapq.heappop(hq)
		if visited[node]:
			continue
		visited[node] = True
		for edge in adj_list[node]:
			(nxt, w, isTrain) = edge
			if not visited[nxt]:
				if d + w < dist[nxt]:
					dist[nxt] = d + w
					if isTrain:
						train_used[nxt] = 1
				if d + w == dist[nxt] and train_used[nxt] == 1 and (not isTrain):
					train_used[nxt] = 0
				heapq.heappush(hq, (d + w, nxt))
	cout << k - sum(train_used) << '\n'

def main():
	solve()
main()