cf449b

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 300030;
long long n, m, k, u, v, x, tr[MAXN], rj, d1, a, b;
vector <pair <long long, long long> > graf[MAXN];
vector <pair <long long, long long> > trn;
priority_queue <pair <long long, long long> > q;
bool bio[MAXN], utr[MAXN];
long long d[MAXN];

void dijkstra () {
    bio[1] = 1;
    for (int i = 0; i < graf[1].size(); i++) {
        q.push(make_pair(-graf[1][i].second, graf[1][i].first));
    }
    for (int i = 0; i < k; i++) {
        d1 = trn[i].first;
        if (!q.empty()) {
            a = -q.top().first;
            b = q.top().second;
        }
        //cout << "Vlak za " << trn[i].second << endl;
        while (!q.empty() && a <= d1) {
            //cout << a << ' ' << b <<  endl;
            q.pop();
            if (!bio[b]) {
                bio[b] = 1;
                d[b] = a;
                for (int j = 0; j < graf[b].size(); j++) {
                    //cout << graf[b][j].second;
                    //cout << "nema gr";
                    if (!bio[graf[b][j].first]) {
                        //cout << "nesto dodao";
                        q.push(make_pair(-d[b] - graf[b][j].second, graf[b][j].first));
                    }
                }
                //cout << "zavrsio for";
            }
            if (!q.empty()) {
                a = -q.top().first;
                b = q.top().second;
            }
        }
        if (!bio[trn[i].second]) {
            q.push(make_pair(-trn[i].first, trn[i].second));
            //cout << "Iskoristio sam vlak " << trn[i].second << endl;
            rj++;
        }
    }
}

int main () {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        scanf ("%I64d %I64d %I64d", &u, &v, &x);
        graf[u].push_back(make_pair(v, x));
        graf[v].push_back(make_pair(u, x));
    }
    for (int i = 0; i < k; i++) {
        scanf ("%I64d %I64d", &u, &x);
        trn.push_back(make_pair(x, u));
    }
    sort(trn.begin(), trn.end());
    dijkstra();
    cout << k - rj;
    return 0;
}