#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 3e5 + 5;
const int MAXQ = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const unsigned long long LINF = 0xffffffffffffffff;
namespace Segment_Tree {
const int MAXP = MAXN * 19;
int ls[MAXP], rs[MAXP], pcnt = 0, n;
void update(int &u, int l, int r, int q) {
  ++pcnt;
  ls[pcnt] = ls[u];
  rs[pcnt] = rs[u];
  u = pcnt;
  if (l == r) {
    ++rs[u];
    return;
  }
  int mid = (l + r) >> 1;
  if (q <= mid)
    update(ls[u], l, mid, q);
  else
    update(rs[u], mid + 1, r, q);
}
int query(int u, int l, int r, int q) {
  if (!u) return 0;
  if (l == r) return rs[u];
  int mid = (l + r) >> 1;
  return q <= mid ? query(ls[u], l, mid, q) : query(rs[u], mid + 1, r, q);
}
inline void update(int &u, int q) { update(u, 1, n, q); }
inline int query(int u, int q) { return query(u, 1, n, q); }
}  // namespace Segment_Tree
using Segment_Tree::query;
using Segment_Tree::update;
unsigned long long c[MAXN];
int seq[MAXN], ord[MAXN], fobi[MAXN], fobt[MAXN];
int tor[MAXN];
int rt[MAXN];
int cnt_del[MAXN];
inline int get_del(int l, int r) { return cnt_del[r] - cnt_del[l - 1]; }
inline int get_eq(int l, int r, int k) {
  return query(rt[r], k) - query(rt[l - 1], k);
}
inline int get_neq(int l, int r, int k) {
  return (r - l + 1) - get_eq(l, r, k) - get_del(l, r);
}
struct Data {
  int id;
  Data(void) {}
  Data(int _id) : id(_id) {}
  inline unsigned long long get(void) const { return c[id]; }
};
inline bool operator==(const Data &p, const Data &q) { return p.id == q.id; }
inline bool operator<(const Data &p, const Data &q) {
  return c[p.id] == c[q.id] ? p.id < q.id : c[p.id] < c[q.id];
}
inline bool operator>(const Data &p, const Data &q) { return q < p; }
inline bool operator<(const Data &p, const pair<int, unsigned long long> &q) {
  return c[p.id] == q.second ? p.id < q.first : c[p.id] < q.second;
}
struct Seg {
  Data mn, sec;
  int l, r;
  Seg(void) {}
  Seg(const Data &_mn, const Data &_sec, int _l, int _r)
      : mn(_mn), sec(_sec), l(_l), r(_r) {}
  Seg(const Data &_mn, const Data &_sec) : mn(_mn), sec(_sec) {}
  inline unsigned long long get(void) const {
    int k2 = get_eq(l, r, mn.id);
    int k1 = r - l + 1 - k2 - get_del(l, r);
    return k1 * c[mn.id] + k2 * c[sec.id];
  }
};
int cmp_way;
inline bool operator<(const Seg &p, const Seg &q) {
  if (cmp_way == 1)
    return p.mn == q.mn ? p.sec == q.sec ? p.l < q.l : p.sec > q.sec
                        : p.mn > q.mn;
  else
    return p.l < q.l;
}
inline bool eq(const Seg &p, const Seg &q) {
  return p.mn == q.mn && p.sec == q.sec;
}
inline Seg upd(const Seg &t, Data k) {
  if (k > t.sec)
    return t;
  else if (k > t.mn)
    return Seg(t.mn, k, t.l, t.r);
  else
    return Seg(k, t.mn, t.l, t.r);
}
vector<int> g[MAXN], gw[MAXN];
pair<int, int> qs[MAXN];
unsigned long long dis[MAXN];
unsigned long long res[MAXQ];
int main(void) {
  int n, m, Q;
  scanf("%d%d%d", &n, &m, &Q);
  for (int i = 1; i <= n; ++i) scanf("%llu", &c[i]);
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    g[u].push_back(v);
    gw[u].push_back(w);
    g[v].push_back(u);
    gw[v].push_back(w);
  }
  for (int i = 1; i <= Q; ++i) {
    scanf("%d%d", &qs[i].first, &qs[i].second);
    c[qs[i].first] += qs[i].second;
  }
  static bool vis[MAXN];
  memset(dis, 0x3f, sizeof(dis));
  priority_queue<pair<unsigned long long, int> > q;
  dis[1] = 0;
  q.push({0, 1});
  while (q.size()) {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = 0; i < (int)g[u].size(); ++i) {
      int v = g[u][i], w = gw[u][i];
      if (dis[v] > dis[u] + w) dis[v] = dis[u] + w, q.push({-dis[v], v});
    }
  }
  fobi[1] = -1;
  for (int u = 1; u <= n; ++u)
    for (int i = 0; i < (int)g[u].size(); ++i) {
      int v = g[u][i], w = gw[u][i];
      if (dis[v] == dis[u] + w) {
        if (fobi[v] == 0)
          fobi[v] = u;
        else
          fobi[v] = -1;
      }
    }
  for (int i = 1; i <= n; ++i) seq[i] = i;
  sort(seq + 1, seq + n + 1, [](int u, int v) { return dis[u] < dis[v]; });
  for (int i = 1; i <= n; ++i) ord[seq[i]] = i;
  for (int i = 1; i <= n; ++i) {
    fobt[i] = fobi[seq[i]];
    cnt_del[i] = cnt_del[i - 1] + (fobt[i] == -1);
  }
  Segment_Tree::n = n + 1;
  for (int i = 1; i <= n; ++i) {
    rt[i] = rt[i - 1];
    if (fobt[i] != -1 && fobt[i] != 1) update(rt[i], fobt[i]);
  }
  tor[n] = n + 1;
  for (int i = n - 1; i >= 1; --i) {
    if (dis[seq[i]] == dis[seq[i + 1]])
      tor[i] = tor[i + 1];
    else
      tor[i] = i + 1;
  }
  c[0] = 0;
  c[MAXN - 1] = LINF;
  Data dinf(MAXN - 1), ndinf(0);
  set<Seg> t;
  cmp_way = 1;
  unsigned long long ans = 0;
  {
    static vector<int> eff[MAXN];
    for (int i = 1; i <= n; ++i) eff[tor[i]].push_back(seq[i]);
    Seg cur(dinf, dinf);
    int lst = 1;
    for (int i = 2; i <= n; ++i) {
      Seg nxt = cur;
      for (int x : eff[i]) nxt = upd(nxt, Data(x));
      if (!eq(nxt, cur) && lst + 1 <= i - 1) {
        cur.l = lst + 1;
        cur.r = i - 1;
        t.insert(cur);
        ans += cur.get();
        lst = i - 1;
      }
      cur = nxt;
    }
    if (lst + 1 <= n) {
      cur.l = lst + 1;
      cur.r = n;
      t.insert(cur);
      ans += cur.get();
    }
  }
  res[Q + 1] = ans;
  for (int k = Q; k >= 1; --k) {
    int x = qs[k].first;
    unsigned long long nc = c[x] - qs[k].second;
    auto itl = t.lower_bound(Seg(x, dinf, -inf, -inf));
    auto it = t.upper_bound(Seg(x, ndinf, inf, inf));
    if (itl != it) {
      --it;
      int l = itl->l, r = it->r;
      int cnt = get_neq(l, r, x);
      ans = ans - (unsigned long long)cnt * c[x] + (unsigned long long)cnt * nc;
      ++it;
    }
    pair<int, unsigned long long> ndat = make_pair(x, nc);
    if (it == t.end() || it->sec < ndat) {
      c[x] = nc;
      res[k] = ans;
      continue;
    }
    int pos = tor[ord[x]];
    if (pos > n)
      it = t.end();
    else if (it->l < pos) {
      cmp_way = 2;
      it = t.lower_bound(Seg(0, 0, pos, pos));
      if (it == t.end() || it->l > pos) {
        assert(it != t.begin());
        --it;
        Seg cur1 = *it, cur2 = cur1;
        t.erase(it);
        cur1.r = pos - 1;
        cur2.l = pos;
        t.insert(cur1);
        it = t.insert(cur2).first;
      }
      cmp_way = 1;
    }
    vector<Seg> nxt;
    while (it != t.end() && !(it->sec < ndat))
      nxt.push_back(*it), t.erase(it++);
    for (Seg &cur : nxt) ans -= cur.get();
    c[x] = nc;
    if (!nxt.size()) {
      res[k] = ans;
      continue;
    }
    for (Seg &cur : nxt) {
      if (cur.sec == x) {
        if (x < cur.mn) swap(cur.mn, cur.sec);
      } else
        cur = upd(cur, x);
    }
    vector<Seg> lst;
    swap(lst, nxt);
    for (Seg &cur : lst) {
      if (nxt.size() && eq(nxt.back(), cur))
        nxt.back().r = cur.r;
      else
        nxt.push_back(cur);
    }
    for (Seg &cur : nxt) ans += cur.get(), t.insert(cur);
    res[k] = ans;
  }
  for (int i = 1; i <= Q + 1; ++i) printf("%llu\n", res[i]);
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

Because the railway system in Gensokyo is often congested, as an enthusiastic engineer, Kawasiro Nitori plans to construct more railway to ease the congestion.

There are n stations numbered from 1 to n and m two-way railways in Gensokyo. Every two-way railway connects two different stations and has a positive integer length d. No two two-way railways connect the same two stations. Besides, it is possible to travel from any station to any other using those railways. Among these n stations, station 1 is the main station. You can get to any station from any other station using only two-way railways.

Because of the technological limitation, Nitori can only construct one-way railways, whose length can be arbitrary positive integer. Constructing a one-way railway from station u will costs w_u units of resources, no matter where the railway ends. To ease the congestion, Nitori plans that after construction there are at least two shortest paths from station 1 to any other station, and these two shortest paths do not pass the same station except station 1 and the terminal. Besides, Nitori also does not want to change the distance of the shortest path from station 1 to any other station.

Due to various reasons, sometimes the cost of building a new railway will increase uncontrollably. There will be a total of q occurrences of this kind of incident, and the i-th event will add additional amount of x_i to the cost of building a new railway from the station k_i.

To save resources, before all incidents and after each incident, Nitori wants you to help her calculate the minimal cost of railway construction.

Input

The first line contains three integers n, m, and q (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m ≤ 3 ⋅ 10^5, 0 ≤ q ≤ 2⋅10^5).

The second line contains n integers w_1,w_2,…,w_n (1 ≤ w_i ≤ 10^9).

Each of the next m lines contains three integers u, v, d (1 ≤ u,v ≤ n, u ≠ v, 1 ≤ d ≤ 10^9), denoting a two-way railway connecting station u and station v, with length d.

The i-th of the next q lines contains two integers k_i,x_i (1 ≤ k_i ≤ n, 1 ≤ x_i ≤ 4 × 10^8).

Output

Print q+1 lines, and the i-th of these lines contains one integer, denoting the minimal cost of railway construction after the i-1-th incident (especially, the 0-th incident means no incident occurred).

Examples

Input


5 5 1
1 1 1 1 1
1 2 1
2 3 1
2 4 1
3 5 1
4 5 1
1 2


Output


3
9


Input


8 11 0
14 4 16 15 1 3 1 14
4 2 1
1 2 3
7 5 4
2 3 1
8 6 2
8 5 5
5 4 5
7 6 7
3 5 5
1 6 6
8 1 4


Output


46


Input


10 16 8
29 1 75 73 51 69 24 17 1 97
1 2 18
2 3 254
2 4 546
2 5 789
5 6 998
6 7 233
7 8 433
1 9 248
5 10 488
2 6 1787
10 8 1176
3 8 2199
4 8 1907
2 10 1277
4 10 731
9 10 1047
1 11
1 9
8 8
1 3
2 19
9 5
9 4
7 6


Output


34
45
54
54
57
76
96
112
112

Note

In the second example, Nitori can build railways as follows: 1 → 2, 1 → 3, 1 → 4, 2 → 8, and the cost is 14 + 14 + 14 + 4 = 46.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 3e5 + 5;
const int MAXQ = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const unsigned long long LINF = 0xffffffffffffffff;
namespace Segment_Tree {
const int MAXP = MAXN * 19;
int ls[MAXP], rs[MAXP], pcnt = 0, n;
void update(int &u, int l, int r, int q) {
  ++pcnt;
  ls[pcnt] = ls[u];
  rs[pcnt] = rs[u];
  u = pcnt;
  if (l == r) {
    ++rs[u];
    return;
  }
  int mid = (l + r) >> 1;
  if (q <= mid)
    update(ls[u], l, mid, q);
  else
    update(rs[u], mid + 1, r, q);
}
int query(int u, int l, int r, int q) {
  if (!u) return 0;
  if (l == r) return rs[u];
  int mid = (l + r) >> 1;
  return q <= mid ? query(ls[u], l, mid, q) : query(rs[u], mid + 1, r, q);
}
inline void update(int &u, int q) { update(u, 1, n, q); }
inline int query(int u, int q) { return query(u, 1, n, q); }
}  // namespace Segment_Tree
using Segment_Tree::query;
using Segment_Tree::update;
unsigned long long c[MAXN];
int seq[MAXN], ord[MAXN], fobi[MAXN], fobt[MAXN];
int tor[MAXN];
int rt[MAXN];
int cnt_del[MAXN];
inline int get_del(int l, int r) { return cnt_del[r] - cnt_del[l - 1]; }
inline int get_eq(int l, int r, int k) {
  return query(rt[r], k) - query(rt[l - 1], k);
}
inline int get_neq(int l, int r, int k) {
  return (r - l + 1) - get_eq(l, r, k) - get_del(l, r);
}
struct Data {
  int id;
  Data(void) {}
  Data(int _id) : id(_id) {}
  inline unsigned long long get(void) const { return c[id]; }
};
inline bool operator==(const Data &p, const Data &q) { return p.id == q.id; }
inline bool operator<(const Data &p, const Data &q) {
  return c[p.id] == c[q.id] ? p.id < q.id : c[p.id] < c[q.id];
}
inline bool operator>(const Data &p, const Data &q) { return q < p; }
inline bool operator<(const Data &p, const pair<int, unsigned long long> &q) {
  return c[p.id] == q.second ? p.id < q.first : c[p.id] < q.second;
}
struct Seg {
  Data mn, sec;
  int l, r;
  Seg(void) {}
  Seg(const Data &_mn, const Data &_sec, int _l, int _r)
      : mn(_mn), sec(_sec), l(_l), r(_r) {}
  Seg(const Data &_mn, const Data &_sec) : mn(_mn), sec(_sec) {}
  inline unsigned long long get(void) const {
    int k2 = get_eq(l, r, mn.id);
    int k1 = r - l + 1 - k2 - get_del(l, r);
    return k1 * c[mn.id] + k2 * c[sec.id];
  }
};
int cmp_way;
inline bool operator<(const Seg &p, const Seg &q) {
  if (cmp_way == 1)
    return p.mn == q.mn ? p.sec == q.sec ? p.l < q.l : p.sec > q.sec
                        : p.mn > q.mn;
  else
    return p.l < q.l;
}
inline bool eq(const Seg &p, const Seg &q) {
  return p.mn == q.mn && p.sec == q.sec;
}
inline Seg upd(const Seg &t, Data k) {
  if (k > t.sec)
    return t;
  else if (k > t.mn)
    return Seg(t.mn, k, t.l, t.r);
  else
    return Seg(k, t.mn, t.l, t.r);
}
vector<int> g[MAXN], gw[MAXN];
pair<int, int> qs[MAXN];
unsigned long long dis[MAXN];
unsigned long long res[MAXQ];
int main(void) {
  int n, m, Q;
  scanf("%d%d%d", &n, &m, &Q);
  for (int i = 1; i <= n; ++i) scanf("%llu", &c[i]);
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    g[u].push_back(v);
    gw[u].push_back(w);
    g[v].push_back(u);
    gw[v].push_back(w);
  }
  for (int i = 1; i <= Q; ++i) {
    scanf("%d%d", &qs[i].first, &qs[i].second);
    c[qs[i].first] += qs[i].second;
  }
  static bool vis[MAXN];
  memset(dis, 0x3f, sizeof(dis));
  priority_queue<pair<unsigned long long, int> > q;
  dis[1] = 0;
  q.push({0, 1});
  while (q.size()) {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = 0; i < (int)g[u].size(); ++i) {
      int v = g[u][i], w = gw[u][i];
      if (dis[v] > dis[u] + w) dis[v] = dis[u] + w, q.push({-dis[v], v});
    }
  }
  fobi[1] = -1;
  for (int u = 1; u <= n; ++u)
    for (int i = 0; i < (int)g[u].size(); ++i) {
      int v = g[u][i], w = gw[u][i];
      if (dis[v] == dis[u] + w) {
        if (fobi[v] == 0)
          fobi[v] = u;
        else
          fobi[v] = -1;
      }
    }
  for (int i = 1; i <= n; ++i) seq[i] = i;
  sort(seq + 1, seq + n + 1, [](int u, int v) { return dis[u] < dis[v]; });
  for (int i = 1; i <= n; ++i) ord[seq[i]] = i;
  for (int i = 1; i <= n; ++i) {
    fobt[i] = fobi[seq[i]];
    cnt_del[i] = cnt_del[i - 1] + (fobt[i] == -1);
  }
  Segment_Tree::n = n + 1;
  for (int i = 1; i <= n; ++i) {
    rt[i] = rt[i - 1];
    if (fobt[i] != -1 && fobt[i] != 1) update(rt[i], fobt[i]);
  }
  tor[n] = n + 1;
  for (int i = n - 1; i >= 1; --i) {
    if (dis[seq[i]] == dis[seq[i + 1]])
      tor[i] = tor[i + 1];
    else
      tor[i] = i + 1;
  }
  c[0] = 0;
  c[MAXN - 1] = LINF;
  Data dinf(MAXN - 1), ndinf(0);
  set<Seg> t;
  cmp_way = 1;
  unsigned long long ans = 0;
  {
    static vector<int> eff[MAXN];
    for (int i = 1; i <= n; ++i) eff[tor[i]].push_back(seq[i]);
    Seg cur(dinf, dinf);
    int lst = 1;
    for (int i = 2; i <= n; ++i) {
      Seg nxt = cur;
      for (int x : eff[i]) nxt = upd(nxt, Data(x));
      if (!eq(nxt, cur) && lst + 1 <= i - 1) {
        cur.l = lst + 1;
        cur.r = i - 1;
        t.insert(cur);
        ans += cur.get();
        lst = i - 1;
      }
      cur = nxt;
    }
    if (lst + 1 <= n) {
      cur.l = lst + 1;
      cur.r = n;
      t.insert(cur);
      ans += cur.get();
    }
  }
  res[Q + 1] = ans;
  for (int k = Q; k >= 1; --k) {
    int x = qs[k].first;
    unsigned long long nc = c[x] - qs[k].second;
    auto itl = t.lower_bound(Seg(x, dinf, -inf, -inf));
    auto it = t.upper_bound(Seg(x, ndinf, inf, inf));
    if (itl != it) {
      --it;
      int l = itl->l, r = it->r;
      int cnt = get_neq(l, r, x);
      ans = ans - (unsigned long long)cnt * c[x] + (unsigned long long)cnt * nc;
      ++it;
    }
    pair<int, unsigned long long> ndat = make_pair(x, nc);
    if (it == t.end() || it->sec < ndat) {
      c[x] = nc;
      res[k] = ans;
      continue;
    }
    int pos = tor[ord[x]];
    if (pos > n)
      it = t.end();
    else if (it->l < pos) {
      cmp_way = 2;
      it = t.lower_bound(Seg(0, 0, pos, pos));
      if (it == t.end() || it->l > pos) {
        assert(it != t.begin());
        --it;
        Seg cur1 = *it, cur2 = cur1;
        t.erase(it);
        cur1.r = pos - 1;
        cur2.l = pos;
        t.insert(cur1);
        it = t.insert(cur2).first;
      }
      cmp_way = 1;
    }
    vector<Seg> nxt;
    while (it != t.end() && !(it->sec < ndat))
      nxt.push_back(*it), t.erase(it++);
    for (Seg &cur : nxt) ans -= cur.get();
    c[x] = nc;
    if (!nxt.size()) {
      res[k] = ans;
      continue;
    }
    for (Seg &cur : nxt) {
      if (cur.sec == x) {
        if (x < cur.mn) swap(cur.mn, cur.sec);
      } else
        cur = upd(cur, x);
    }
    vector<Seg> lst;
    swap(lst, nxt);
    for (Seg &cur : lst) {
      if (nxt.size() && eq(nxt.back(), cur))
        nxt.back().r = cur.r;
      else
        nxt.push_back(cur);
    }
    for (Seg &cur : nxt) ans += cur.get(), t.insert(cur);
    res[k] = ans;
  }
  for (int i = 1; i <= Q + 1; ++i) printf("%llu\n", res[i]);
  return 0;
}

```