#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll inf = 0x3f3f3f3f3f3f3f3f;

const int mod = 998244353;

void add(int &x, int y) { if ((x += y - mod) < 0) x += mod; }

const int N = 5e4;

ll n;
int m, q;
vector<pair<int, ll>> e0;
vector<vector<ll>> d;
vector<tuple<int, ll, ll>> e1;

int countComponents(ll n, vector<ll> &d) {
  int ret = 0;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pQ;
  for (ll i : d) pQ.emplace(i, i); d.clear();
  ll tag = 0;
  while (!pQ.empty()) {
    auto [d0, t] = pQ.top(); pQ.pop(), d0 -= tag;
    if (!d0) continue; d.push_back(t); if (n < d0) break;
    ll d1 = pQ.empty() ? inf : pQ.top().first - tag;
    ll k = min(n, d1) / d0; n -= k * d0, tag += k * d0, pQ.emplace(d0 + tag, t);
    if (n < d0) ret = (ret + d0 - n) % mod;
  }
  sort(d.begin(), d.end()), d.erase(unique(d.begin(), d.end()), d.end());
  return ret = (ret + n) % mod;
}

auto getComponents(ll n, vector<ll> d, vector<ll> s) {
  vector<pair<ll, ll>> ret;
  for (ll u : s) ret.emplace_back(u, u);
  priority_queue<ll, vector<ll>, greater<ll>> pQ(d.begin(), d.end());
  ll tag = 0;
  while (!pQ.empty()) {
    auto d0 = pQ.top(); pQ.pop(), d0 -= tag;
    if (!d0) continue; if (n < d0) break;
    ll d1 = pQ.empty() ? inf : pQ.top() - tag;
    ll k = min(n, d1) / d0; n -= k * d0, tag += k * d0, pQ.push(d0 + tag);
    for (int i = 0; i < ret.size(); ++i) {
      ll &u = ret[i].first;
      if (u >= n + k * d0) continue;
      u -= max<ll>(k - 1 - (n + k * d0 - u - 1) / d0, 0) * d0;
      if (u >= d0 && u >= n) u -= d0;
    }
  }
  return ret;
}

int ans;

void solve(int l, int r, vector<vector<ll>> vec) {
  if (vec.empty()) return ;
  if (l == r) {
    for (auto s : vec) {
      if (s.empty()) continue;
      ans = (ans + (ll)(mod - s.size() + 1) * e0[l].first) % mod;
      for (int i = 1; i < s.size(); ++i) e1.emplace_back(e0[l].first, s[0], s[i]);
    }
    return ;
  }
  int mid = (l + r) >> 1;
  vector<vector<ll>> L, R;
  for (auto s : vec) {
    if (s.empty()) continue;
    auto res = getComponents(n, d[mid], s); sort(res.begin(), res.end());
    R.emplace_back();
    for (int i = 0, j; i < res.size(); i = j + 1) {
      L.emplace_back(1, res[i].second), R.back().push_back(res[i].second);
      for (j = i; j + 1 < res.size() && res[j + 1].first == res[i].first; ++j)
        L.back().push_back(res[j + 1].second);
    }
  }
  solve(l, mid, L), solve(mid + 1, r, R);
}

struct UnionFind {
  vector<int> fa;
  UnionFind(int n) : fa(n, -1) {}
  bool isRoot(int u) { return !~fa[u]; }
  int find(int u) { return isRoot(u) ? u : fa[u] = find(fa[u]); }
  bool merge(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu == fv) return 0;
    fa[fv] = fu; return 1;
  }
};

int main() {
  scanf("%lld%d%d", &n, &m, &q), e0.resize(m), e1.resize(q);
  for (auto &[x, d] : e0) scanf("%lld%d", &d, &x);
  sort(e0.begin(), e0.end()), d.resize(m);
  int cnt = n % mod;
  for (int i = 0; i < m; ++i) {
    auto [x, d0] = e0[i];
    ans = (ans + (ll)x * cnt) % mod, d[i].push_back(d0),
    ans = (ans + (ll)(mod - x) * (cnt = countComponents(n, d[i]))) % mod;
    if (i + 1 < m) d[i + 1] = d[i];
  }
  vector<ll> s;
  for (auto &[w, u, v] : e1) scanf("%lld%lld%d", &u, &v, &w), s.push_back(u), s.push_back(v);
  sort(s.begin(), s.end()), s.erase(unique(s.begin(), s.end()), s.end());
  if (m) {
    auto res = getComponents(n, d[m - 1], s); sort(res.begin(), res.end());
    vector<vector<ll>> vec;
    for (int i = 0, j; i < res.size(); i = j + 1) {
      vec.emplace_back(1, res[i].second);
      for (j = i; j + 1 < res.size() && res[j + 1].first == res[i].first; ++j)
        vec.back().push_back(res[j + 1].second);
    }
    solve(0, m - 1, vec);
  }
  sort(e1.begin(), e1.end()); UnionFind uf(s.size());
  for (auto [w, u, v] : e1) {
    u = lower_bound(s.begin(), s.end(), u) - s.begin(),
    v = lower_bound(s.begin(), s.end(), v) - s.begin();
    if (uf.merge(u, v)) add(ans, w);
  }
  printf("%d\n", ans);
}