cf449b.cpp

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

const int MAX_N = 100007;
const ll Inf = (ll)1e18;

struct edge {
	int b, c;
	bool sp;
	edge(int b = 0, int c = 0, int sp = false) :b(b),c(c),sp(sp) {
	}
};

int n, m, k;
vector<edge> E;
vector<int> neigh[MAX_N];
ll dist[MAX_N];
vector<pii> srt;

void addedge(int a, int b, int c, bool sp) {
	neigh[a].push_back(E.size()); E.push_back(edge(b, c, sp));
	neigh[b].push_back(E.size()); E.push_back(edge(a, c, sp));
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	while (m -- > 0) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		addedge(a, b, c, false);
	}
	for (int i = 0; i < k; ++i) {
		int b, c;
		scanf("%d%d", &b, &c);
		addedge(1, b, c, true);
	}
	fill(dist, dist + n + 1, Inf);
	dist[1] = 0;
	priority_queue<pii> Q;Q.push(pii(0, 1));
	while (!Q.empty()) {
		int v = Q.top().second;
		ll d = -Q.top().first; Q.pop();
		if (dist[v] != d) continue;
		srt.push_back(pii(d, v));
		for (int i = 0; i < neigh[v].size(); ++i) {
			int e = neigh[v][i];
			if (d + E[e].c < dist[E[e].b]) {
				dist[E[e].b] = d + E[e].c;
				Q.push(pii(-dist[E[e].b], E[e].b));
			}
		}
	}
	sort(srt.begin(), srt.end());
	for (int i = srt.size() - 1; i > 0; --i) {
		int v = srt[i].second;
		bool found = false;
		for (int j = 0; j < neigh[v].size() && !found; ++j) {
			int e = neigh[v][j];
			found = !E[e].sp && dist[E[e].b] + E[e].c == dist[v];
		}
		k -= !found;
	}
	printf("%d\n", k);
	return 0;
}