ソースコード
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
for (auto &i : v) is >> i;
return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
const string delimiter = "\n";
REP(i, v.size())
{
os << v[i];
if (i != v.size() - 1) os << delimiter;
}
return os;
}
/*--------------------template--------------------*/
typedef int Weight;
struct Edge
{
int from, to; Weight cost;
bool operator < (const Edge& e) const { return cost < e.cost; }
bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph &g, int from, int to, Weight cost)
{
g[from].push_back(Edge{ from, to, cost });
}
int main()
{
cin.sync_with_stdio(false); cout << fixed << setprecision(10);
int n, m, k;
cin >> n >> m >> k;
Graph g(n);
REP(i, m)
{
int a, b, c; cin >> a >> b >> c;
a--; b--;
add_edge(g, a, b, c);
add_edge(g, b, a, c);
}
vi d(n, -1);
typedef pair<Weight, int> P;
priority_queue<P, vector<P>, greater<P>> que;
REP(i, k)
{
int a, b; cin >> a >> b;
a--;
d[a] = b;
que.push(P(b, a));
}
while (!que.empty())
{
int p = que.top().first, v = que.top().second;
que.pop();
if (d[v] > p) continue;
for (auto e : g[v])
{
int u = e.to;
int c = e.cost;
if (p >= c && d[u] < p - c)
{
d[u] = p - c;
que.push(P(d[u], u));
}
}
}
int ans = 0;
for (auto i : d) ans += i >= 0;
cout << ans << endl;
return 0;
}