ソースコード
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.AbstractCollection;
import java.util.List;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
MyInput in = new MyInput(inputStream);
PrintWriter out = new PrintWriter(outputStream);
TaskG solver = new TaskG();
solver.solve(1, in, out);
out.close();
}
static class TaskG {
public void solve(int testNumber, MyInput in, PrintWriter out) {
int n = in.nextInt();
int m = in.nextInt();
int k = in.nextInt();
Graph g = new Graph(n);
for (int i = 0; i < m; i++) {
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
int c = in.nextInt();
g.addEdge(a, b, c, i);
g.addEdge(b, a, c, i);
}
int[] max = new int[n];
Arrays.fill(max, -1);
PriorityQueue<Long> que = new PriorityQueue<>(Comparator.comparingLong(x -> -x));
for (int i = 0; i < k; i++) {
int h = in.nextInt() - 1;
int d = in.nextInt();
que.add((long) d << 32 | h);
max[h] = d;
}
while (!que.isEmpty()) {
long x = que.poll();
int d = (int) (x >>> 32);
int i = (int) (x & 0xFFFFFFFFL);
if (max[i] != d) continue;
for (Edge e : g.vertex[i].edges) {
int c = (int) (d - e.cost);
if (c <= max[e.to]) continue;
max[e.to] = c;
que.add((long) c << 32 | e.to);
}
}
out.println(Arrays.stream(max).filter(x -> x >= 0).count());
}
class Edge {
public final int edgeId;
public final int to;
public long cost;
public Edge(int to, long cost, int edgeId) {
this.to = to;
this.cost = cost;
this.edgeId = edgeId;
}
public String toString() {
return String.format("[Edge id=%d, to=%d, cost=%d]", edgeId, to, cost);
}
}
class Vertex {
public final int id;
public final List<Edge> edges = new ArrayList<>();
public Vertex(final int id) {
this.id = id;
}
public void addEdge(Edge e) {
edges.add(e);
}
}
class Graph {
int V;
int E;
Vertex[] vertex;
public Graph(int V) {
this.V = V;
this.E = 0;
vertex = new Vertex[V];
for (int i = 0; i < V; i++) vertex[i] = new Vertex(i);
}
public void addEdge(int s, int t, long c, int edgeId) {
vertex[s].addEdge(new Edge(t, c, edgeId));
}
}
}
static class MyInput {
private final BufferedReader in;
private static int pos;
private static int readLen;
private static final char[] buffer = new char[1024 * 8];
private static char[] str = new char[500 * 8 * 2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];
static {
for (int i = 0; i < 10; i++) {
isDigit['0' + i] = true;
}
isDigit['-'] = true;
isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
isLineSep['\r'] = isLineSep['\n'] = true;
}
public MyInput(InputStream is) {
in = new BufferedReader(new InputStreamReader(is));
}
public int read() {
if (pos >= readLen) {
pos = 0;
try {
readLen = in.read(buffer);
} catch (IOException e) {
throw new RuntimeException();
}
if (readLen <= 0) {
throw new MyInput.EndOfFileRuntimeException();
}
}
return buffer[pos++];
}
public int nextInt() {
int len = 0;
str[len++] = nextChar();
len = reads(len, isSpace);
int i = 0;
int ret = 0;
if (str[0] == '-') {
i = 1;
}
for (; i < len; i++) ret = ret * 10 + str[i] - '0';
if (str[0] == '-') {
ret = -ret;
}
return ret;
}
public char nextChar() {
while (true) {
final int c = read();
if (!isSpace[c]) {
return (char) c;
}
}
}
int reads(int len, boolean[] accept) {
try {
while (true) {
final int c = read();
if (accept[c]) {
break;
}
if (str.length == len) {
char[] rep = new char[str.length * 3 / 2];
System.arraycopy(str, 0, rep, 0, str.length);
str = rep;
}
str[len++] = (char) c;
}
} catch (MyInput.EndOfFileRuntimeException e) {
}
return len;
}
static class EndOfFileRuntimeException extends RuntimeException {
}
}
}