#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void Print() { cout << endl; }
template <typename T1, typename... T>
void Print(const T1 &t1, const T &...t) {
  cout << t1 << " ";
  Print(t...);
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class Iterator>
ostream &output_cantainer(ostream &os, Iterator first, Iterator last,
                          bool space = true) {
  if (space) {
    for (Iterator it = first; it != last; it++) {
      os << (*it) << ' ';
    }
    os << endl;
  } else
    for (Iterator it = first; it != last; it++) {
      os << (*it) << endl;
    }
  return os;
}
struct BigInt {
  static const int base = 1e9;
  static const int base_digits = 9;
  vector<int> z;
  int sign;
  BigInt() : sign(1) {}
  BigInt(long long v) : sign(1) {
    if (v < 0) sign = -1, v = -v;
    for (; v > 0; v = v / base) z.push_back(v % base);
  }
  BigInt(const string &s) { read(s); }
  BigInt(const BigInt &rhs) : z(rhs.z), sign(rhs.sign) {}
  friend void swap(BigInt &lhs, BigInt &rhs) {
    lhs.z.swap(rhs.z);
    std::swap(lhs.sign, rhs.sign);
  }
  void read(const string &s) {
    sign = 1;
    z.clear();
    int pos = 0, l = s.size();
    while (pos < l && (s[pos] == '+' || s[pos] == '-')) {
      if (s[pos] == '-') sign = -sign;
      ++pos;
    }
    for (int i = l - 1; i >= pos; i -= base_digits) {
      int x = 0;
      for (int j = max(pos, i - base_digits + 1); j <= i; j++) {
        x = x * 10 + s[j] - '0';
      }
      z.push_back(x);
    }
    trim();
  }
  BigInt &operator=(BigInt rhs) {
    swap(*this, rhs);
    return *this;
  }
  BigInt &operator=(long long v) {
    BigInt rhs(v);
    swap(*this, rhs);
    return *this;
  }
  BigInt operator+(const BigInt &rhs) {
    BigInt res(*this);
    res += rhs;
    return res;
  }
  BigInt &operator+=(const BigInt &rhs) {
    if (sign == rhs.sign) {
      for (int i = 0, carry = 0, u = max(z.size(), rhs.z.size());
           i < u || carry; i++) {
        if (i == z.size()) z.push_back(0);
        z[i] += carry + (i < (int)rhs.z.size() ? rhs.z[i] : 0);
        carry = z[i] >= base;
        if (carry) z[i] -= base;
      }
      return *this;
    }
    return (*this -= (-rhs));
  }
  BigInt operator-() const {
    BigInt res(*this);
    res.sign = -res.sign;
    return res;
  }
  BigInt operator-(const BigInt &rhs) const {
    BigInt res(*this);
    res -= rhs;
    return res;
  }
  BigInt &operator-=(const BigInt &rhs) {
    if (sign == rhs.sign) {
      if (abs() >= rhs.abs()) {
        for (int i = 0, carry = 0; i < (int)rhs.z.size() || carry; ++i) {
          z[i] -= carry + (i < (int)rhs.z.size() ? rhs.z[i] : 0);
          carry = z[i] < 0;
          if (carry) z[i] += base;
        }
        trim();
        return *this;
      }
      BigInt target(rhs - *this);
      target.neg();
      swap(*this, target);
      return *this;
    }
    return *this += (-rhs);
  }
  bool operator<(const BigInt &rhs) const {
    if (sign != rhs.sign) return sign < rhs.sign;
    if (z.size() != rhs.z.size())
      return (int)z.size() * sign < (int)rhs.z.size() * rhs.sign;
    for (int i = z.size() - 1; i >= 0; i--)
      if (z[i] != rhs.z[i]) return z[i] * sign < rhs.z[i] * sign;
    return false;
  }
  bool operator<=(const BigInt &rhs) const { return !(rhs < *this); }
  bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
  void neg() { sign = -sign; }
  void trim() {
    while (!z.empty() && z.back() == 0) z.pop_back();
    if (z.empty()) sign = 1;
  }
  bool isZero() const { return z.empty() || (z.size() == 1 && !z[0]); }
  BigInt abs() const {
    BigInt res(*this);
    res.sign *= res.sign;
    return res;
  }
  friend ostream &operator<<(ostream &os, const BigInt &v) {
    if (v.sign == -1) os << '-';
    os << ((v.z.empty()) ? 0 : v.z.back());
    for (int i = (int)v.z.size() - 2; i >= 0; --i)
      os << setw(base_digits) << setfill('0') << v.z[i];
    return os;
  }
  friend istream &operator>>(istream &is, BigInt &v) {
    string s;
    is >> s;
    v.read(s);
    return is;
  }
};
const int N = 1e5 + 4;
const long long INF = 1ll << 62;
int n, m, k;
struct E {
  int to, w;
  E() = default;
  E(int _to, int _w) : to(_to), w(_w) {}
};
vector<E> ed[N], et;
long long dis1[N];
int ans;
void dij1() {
  multiset<pair<long long, int> > ts1, ts2;
  fill(dis1, dis1 + n + 1, INF);
  ts1.insert((make_pair((0), (1))));
  dis1[1] = 0;
  for (auto &e : et) ts2.insert((make_pair((e.w), (e.to))));
  while (!ts1.empty() || !ts2.empty()) {
    if (!ts1.empty()) {
      auto top = *(ts1.begin());
      int x = top.second;
      long long d = top.first;
      if (!ts2.empty() && d > ts2.begin()->first) {
        x = ts2.begin()->second;
        d = ts2.begin()->first;
        ts2.erase(ts2.begin());
        if (dis1[x] <= d) {
          ans++;
          continue;
        }
        if (dis1[x] != INF) ts1.erase((make_pair((dis1[x]), (x))));
        dis1[x] = d;
        ts1.insert((make_pair((d), (x))));
      } else {
        ts1.erase(ts1.begin());
        for (auto &e : ed[x]) {
          int y = e.to;
          long long nd = d + e.w;
          if (nd >= dis1[y]) continue;
          if (dis1[y] != INF) ts1.erase((make_pair((dis1[y]), (y))));
          dis1[y] = nd;
          ts1.insert((make_pair((nd), (y))));
        }
      }
    } else {
      auto top = *(ts2.begin());
      ts2.erase(ts2.begin());
      int x = top.second;
      long long d = top.first;
      if (dis1[x] <= d) {
        ans++;
        continue;
      }
      if (dis1[x] != INF) ts1.erase((make_pair((dis1[x]), (x))));
      dis1[x] = d;
      ts1.insert((make_pair((d), (x))));
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    ((ed[u]).push_back((E(v, w))));
    ((ed[v]).push_back((E(u, w))));
  }
  for (int i = 1; i <= k; i++) {
    int v, w;
    scanf("%d%d", &v, &w);
    ((et).push_back((E(v, w))));
  }
  dij1();
  printf("%d\n", ans);
}

### Prompt

Your task is to create a CPP solution to the following problem:

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 ui to vi (and vise versa) using the i-th road, the length of this road is xi. 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 si (and vise versa), the length of this route is yi.

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 ≤ 105; 1 ≤ m ≤ 3·105; 1 ≤ k ≤ 105).

Each of the next m lines contains three integers ui, vi, xi (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ xi ≤ 109).

Each of the next k lines contains two integers si and yi (2 ≤ si ≤ n; 1 ≤ yi ≤ 109).

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void Print() { cout << endl; }
template <typename T1, typename... T>
void Print(const T1 &t1, const T &...t) {
  cout << t1 << " ";
  Print(t...);
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class Iterator>
ostream &output_cantainer(ostream &os, Iterator first, Iterator last,
                          bool space = true) {
  if (space) {
    for (Iterator it = first; it != last; it++) {
      os << (*it) << ' ';
    }
    os << endl;
  } else
    for (Iterator it = first; it != last; it++) {
      os << (*it) << endl;
    }
  return os;
}
struct BigInt {
  static const int base = 1e9;
  static const int base_digits = 9;
  vector<int> z;
  int sign;
  BigInt() : sign(1) {}
  BigInt(long long v) : sign(1) {
    if (v < 0) sign = -1, v = -v;
    for (; v > 0; v = v / base) z.push_back(v % base);
  }
  BigInt(const string &s) { read(s); }
  BigInt(const BigInt &rhs) : z(rhs.z), sign(rhs.sign) {}
  friend void swap(BigInt &lhs, BigInt &rhs) {
    lhs.z.swap(rhs.z);
    std::swap(lhs.sign, rhs.sign);
  }
  void read(const string &s) {
    sign = 1;
    z.clear();
    int pos = 0, l = s.size();
    while (pos < l && (s[pos] == '+' || s[pos] == '-')) {
      if (s[pos] == '-') sign = -sign;
      ++pos;
    }
    for (int i = l - 1; i >= pos; i -= base_digits) {
      int x = 0;
      for (int j = max(pos, i - base_digits + 1); j <= i; j++) {
        x = x * 10 + s[j] - '0';
      }
      z.push_back(x);
    }
    trim();
  }
  BigInt &operator=(BigInt rhs) {
    swap(*this, rhs);
    return *this;
  }
  BigInt &operator=(long long v) {
    BigInt rhs(v);
    swap(*this, rhs);
    return *this;
  }
  BigInt operator+(const BigInt &rhs) {
    BigInt res(*this);
    res += rhs;
    return res;
  }
  BigInt &operator+=(const BigInt &rhs) {
    if (sign == rhs.sign) {
      for (int i = 0, carry = 0, u = max(z.size(), rhs.z.size());
           i < u || carry; i++) {
        if (i == z.size()) z.push_back(0);
        z[i] += carry + (i < (int)rhs.z.size() ? rhs.z[i] : 0);
        carry = z[i] >= base;
        if (carry) z[i] -= base;
      }
      return *this;
    }
    return (*this -= (-rhs));
  }
  BigInt operator-() const {
    BigInt res(*this);
    res.sign = -res.sign;
    return res;
  }
  BigInt operator-(const BigInt &rhs) const {
    BigInt res(*this);
    res -= rhs;
    return res;
  }
  BigInt &operator-=(const BigInt &rhs) {
    if (sign == rhs.sign) {
      if (abs() >= rhs.abs()) {
        for (int i = 0, carry = 0; i < (int)rhs.z.size() || carry; ++i) {
          z[i] -= carry + (i < (int)rhs.z.size() ? rhs.z[i] : 0);
          carry = z[i] < 0;
          if (carry) z[i] += base;
        }
        trim();
        return *this;
      }
      BigInt target(rhs - *this);
      target.neg();
      swap(*this, target);
      return *this;
    }
    return *this += (-rhs);
  }
  bool operator<(const BigInt &rhs) const {
    if (sign != rhs.sign) return sign < rhs.sign;
    if (z.size() != rhs.z.size())
      return (int)z.size() * sign < (int)rhs.z.size() * rhs.sign;
    for (int i = z.size() - 1; i >= 0; i--)
      if (z[i] != rhs.z[i]) return z[i] * sign < rhs.z[i] * sign;
    return false;
  }
  bool operator<=(const BigInt &rhs) const { return !(rhs < *this); }
  bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
  void neg() { sign = -sign; }
  void trim() {
    while (!z.empty() && z.back() == 0) z.pop_back();
    if (z.empty()) sign = 1;
  }
  bool isZero() const { return z.empty() || (z.size() == 1 && !z[0]); }
  BigInt abs() const {
    BigInt res(*this);
    res.sign *= res.sign;
    return res;
  }
  friend ostream &operator<<(ostream &os, const BigInt &v) {
    if (v.sign == -1) os << '-';
    os << ((v.z.empty()) ? 0 : v.z.back());
    for (int i = (int)v.z.size() - 2; i >= 0; --i)
      os << setw(base_digits) << setfill('0') << v.z[i];
    return os;
  }
  friend istream &operator>>(istream &is, BigInt &v) {
    string s;
    is >> s;
    v.read(s);
    return is;
  }
};
const int N = 1e5 + 4;
const long long INF = 1ll << 62;
int n, m, k;
struct E {
  int to, w;
  E() = default;
  E(int _to, int _w) : to(_to), w(_w) {}
};
vector<E> ed[N], et;
long long dis1[N];
int ans;
void dij1() {
  multiset<pair<long long, int> > ts1, ts2;
  fill(dis1, dis1 + n + 1, INF);
  ts1.insert((make_pair((0), (1))));
  dis1[1] = 0;
  for (auto &e : et) ts2.insert((make_pair((e.w), (e.to))));
  while (!ts1.empty() || !ts2.empty()) {
    if (!ts1.empty()) {
      auto top = *(ts1.begin());
      int x = top.second;
      long long d = top.first;
      if (!ts2.empty() && d > ts2.begin()->first) {
        x = ts2.begin()->second;
        d = ts2.begin()->first;
        ts2.erase(ts2.begin());
        if (dis1[x] <= d) {
          ans++;
          continue;
        }
        if (dis1[x] != INF) ts1.erase((make_pair((dis1[x]), (x))));
        dis1[x] = d;
        ts1.insert((make_pair((d), (x))));
      } else {
        ts1.erase(ts1.begin());
        for (auto &e : ed[x]) {
          int y = e.to;
          long long nd = d + e.w;
          if (nd >= dis1[y]) continue;
          if (dis1[y] != INF) ts1.erase((make_pair((dis1[y]), (y))));
          dis1[y] = nd;
          ts1.insert((make_pair((nd), (y))));
        }
      }
    } else {
      auto top = *(ts2.begin());
      ts2.erase(ts2.begin());
      int x = top.second;
      long long d = top.first;
      if (dis1[x] <= d) {
        ans++;
        continue;
      }
      if (dis1[x] != INF) ts1.erase((make_pair((dis1[x]), (x))));
      dis1[x] = d;
      ts1.insert((make_pair((d), (x))));
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    ((ed[u]).push_back((E(v, w))));
    ((ed[v]).push_back((E(u, w))));
  }
  for (int i = 1; i <= k; i++) {
    int v, w;
    scanf("%d%d", &v, &w);
    ((et).push_back((E(v, w))));
  }
  dij1();
  printf("%d\n", ans);
}

```