<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

529. It's Time to Repair the Roads
Time limit per test: 2.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Everybody knows about the problems with roads in Berland. The government has been trying to undertake major repairs for many years, but the roads have never been repaired due to the lack of money in the budget.

There are n cities and m roads in Berland. The cities are numbered from 1 to n. The roads are numbered from 1 to m. Each road connects a pair of different cities, all the roads are two-way. There is at most one road between any pair of cities. The cost of repairing is known for each road.

Clearly, repairing all roads in Berland is an unaffordable luxury, so the government decided to repair only such set of the roads, that it's possible to get from any city to any other city by the roads from this repaired set, and the total cost of these road works is minimal.

In the circumstances of the global economic crisis and global warming, road repair costs change every day. Berland's scientists managed to predict these changes, concluding that the cost of road works will change for only one road each day. They created a full list of expected changes for the coming t days — for each day they came up a road and its new repair cost.

The government of Berland would like to know when it would be better to repair the roads, so they need to figure out the cost of road works for every of the coming t days before making a final decision. Your task is to help them and figure out the total repair cost of Berland's road system at the end of each these t days. As repair costs change over time, the set of selected roads can change on a daily basis as well.

Input
The first line contains a pair of integers n,m (2 ≤ n ≤ 40000, n - 1 ≤ m ≤ 40000), where n — the amount of cities, m — the amount of roads. Each of the following m lines contains a road description: three integer numbers xi, yi and pi (1 ≤ xi, yi ≤ n, xi ≠ yi, 1 ≤ pi ≤ 40000), where xi and yi are indices of the cities connected by the given road, and pi — initial cost of repairing it.

Then there follows a line with the only number t (1 ≤ t ≤ 40000), t — amount of days. The following t lines contain the scientists' predictions for the coming t days. Each of t lines contains a pair of integer numbers ei, ci (1 ≤ ei ≤ m, 1 ≤ ci ≤ 40000), where ci — is the new repair cost for the road ei.

It's possible to get from any city to any other city by the roads. The cost of repair for a single road can be changed more than once over time.

Output
Output t lines, each of them should contain the road system's total repair cost at the end of each day.

Example(s)
sample input
sample output
4 6
1 2 10
2 3 20
2 4 30
1 3 40
3 4 50
4 1 60
3
4 22
5 17
4 14
60
47
41

sample input
sample output
3 3
3 2 4
3 1 4
2 1 3
3
2 5
2 2
2 5
7
5
7

<|response|>
1. Abridged Problem Statement
You have an undirected connected graph with n vertices and m edges, each edge having an initial weight. There are t days; on day i, the weight of one specified edge is changed. After each change, report the total weight of the minimum spanning tree (MST) of the current graph.

2. Key Observations
a. Recomputing the MST from scratch in O(m log m) per update is too slow for m,t up to 4·10^4.
b. We can process the t updates offline in blocks of size B (e.g. B≈200).
c. In each block:
   - Mark the B edges that will change.
   - Build a "baseline" MST ignoring those B edges (one DSU pass over all m edges).
   - Contract each connected component of this baseline MST into a super-node.
   - Among the non-updated edges, pick those that still connect different super-nodes—these are at most n–1 edges.
   - Append the B updated edges (with their current weights) to form a small list of size ≲n+B. Sort it once.
   - For each query in the block: adjust the one changed edge's weight in that small list (by two bubble passes over the nearly-sorted array) and rerun Kruskal on ≲n+B edges to get the new MST cost in O((n+B) α(n)).
   - Finally merge the updated edges back into the global sorted-by-weight edge list in O(m+B) to prepare for the next block.

3. Full Solution Approach
Let ed[0…m−1] be the array of edges kept sorted by current weight (field .i stores the original 0-based edge id). Let que[0…t−1] be queries (edge_id, new_weight). Maintain pos_edge[edge_id] = index of that edge in ed[]. Use boolean arrays used[edge_id] and used2[edge_id] for the block bookkeeping.

- Preprocess: sort ed by weight; record pos_edge[edge_id] for each edge.
- Process queries in blocks of size B: for block [st…en]:
  1. Mark used[que[i].first]=1 for each i in the block (edge IDs of changing edges).
  2. Baseline pass: initialize DSUs tmp and additional_d on n vertices. For each non-touched edge, pre-unite via tmp the touched edges (to correctly check connectivity including the touched edges); then sweep non-touched edges in weight order: if not yet connected in tmp, unite in both tmp and additional_d, add weight to sum.
  3. Compress: assign comp_id for each root in additional_d, giving cnt super-nodes.
  4. Extract important edges: using DSU d on cnt super-nodes, sweep non-touched edges in weight order; if the super-node endpoints are not yet connected, add edge to important[] and mark used2[edge.i]=1.
  5. Append touched edges to important[] and sort all of important[] by weight.
  6. For each query i in [st…en]: update the weight of the edge in important[], restore sorted order with a single forward bubble pass then a single backward bubble pass, run Kruskal on important[] with a fresh DSU on cnt super-nodes starting from sum, record answer[i].
  7. Merge ed[] and important[] back together (skipping touched entries and used2 entries already in ed[]) using two pointers; rebuild pos_edge[].
- Output answer[0…t−1].

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int MAXN = (1 << 20);
const int B = 200;

struct DSU {
    int n;
    vector<int> par, sz;

    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 1);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
        }
    }

    int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
    bool connected(int u, int v) { return root(u) == root(v); }

    void unite(int u, int v) {
        u = root(u);
        v = root(v);
        if(u == v) {
            return;
        }

        if(sz[u] < sz[v]) {
            swap(u, v);
        }

        par[v] = u;
        sz[u] += sz[v];
    }
};

struct Edge {
    int u, v, w, i;
    Edge() { u = v = w = i = 0; }

    Edge(int _u, int _v, int _w, int _i) {
        u = _u;
        v = _v;
        w = _w;
        i = _i;
    }
};

bool cmp(const Edge& x, const Edge& y) { return x.w < y.w; }

int n, m;
Edge ed[MAXN], nw_li[MAXN], important[MAXN];
pair<int, int> que[MAXN];

void read() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
        ed[i].i = i;
    }
}

int64_t answer[MAXN];
int pos_edge[MAXN], imp_sz;
bool used[MAXN], used2[MAXN];
int comp_id[MAXN];
DSU additional_d, tmp, d;

int get(int x) { return comp_id[additional_d.root(x)]; }

void solve() {
    // Offline dynamic MST via sqrt-decomposition on the t queries. Edges are
    // kept globally sorted by weight (ed[], indexed by original id through
    // pos_edge). Queries are processed in blocks of B. For one block:
    //
    // The edges touched by the block (used[]) are contracted away from the
    // rest. We run Kruskal on the remaining, untouched edges to glue together
    // everything they can connect; additional_d holds those forced unions and
    // sum accumulates their fixed contribution. The contracted vertices are
    // relabelled into cnt super-nodes via comp_id, so get(x) maps an original
    // vertex to its super-node.
    //
    // Within that contracted graph only O(cnt) untouched edges can ever matter
    // for an MST (one per merge a fresh Kruskal would make); we extract them as
    // the "important" set and append the block's touched edges. For each query
    // we set the new weight on the affected edge, re-sort the small important
    // list by a couple of bubble passes (it stays nearly sorted), and rerun
    // Kruskal over the super-nodes, adding the result to the precomputed sum.
    //
    // After the block we merge the touched edges back into the global sorted
    // order so the next block starts from a fully sorted ed[] again.

    sort(ed, ed + m, cmp);
    for(int i = 0; i < m; i++) {
        pos_edge[ed[i].i] = i;
    }

    int q;
    cin >> q;

    for(int i = 0; i < q; i++) {
        cin >> que[i].first >> que[i].second;
        que[i].first--;
    }

    for(int st = 0; st < q; st += B) {
        int en = min(q - 1, st + B - 1);
        for(int i = 0; i < m; i++) {
            used[i] = used2[i] = 0;
        }

        for(int i = st; i <= en; i++) {
            used[que[i].first] = 1;
        }

        tmp.init(n);
        additional_d.init(n);
        for(int i = 0; i < m; i++) {
            if(used[ed[i].i]) {
                tmp.unite(ed[i].u, ed[i].v);
            }
        }

        int64_t sum = 0;
        for(int i = 0; i < m; i++) {
            if(!used[ed[i].i] && !tmp.connected(ed[i].u, ed[i].v)) {
                sum += ed[i].w;
                tmp.unite(ed[i].u, ed[i].v);
                additional_d.unite(ed[i].u, ed[i].v);
            }
        }

        int cnt = 0;
        for(int i = st; i <= en; i++) {
            answer[i] = sum;
        }

        for(int i = 1; i <= n; i++) {
            if(i == additional_d.root(i)) {
                comp_id[i] = cnt++;
            }
        }

        d.init(cnt);
        imp_sz = 0;
        for(int i = 0; i < m; i++) {
            if(used[ed[i].i]) {
                continue;
            }

            int u = get(ed[i].u), v = get(ed[i].v);
            if(!d.connected(u, v)) {
                d.unite(u, v);
                important[imp_sz++] = ed[i];
            }
        }

        for(int i = 0; i < imp_sz; i++) {
            used2[important[i].i] = 1;
        }

        for(int i = 0; i < m; i++) {
            if(used[ed[i].i]) {
                important[imp_sz++] = ed[i];
            }
        }

        sort(important, important + imp_sz, cmp);

        for(int i = st; i <= en; i++) {
            int w = que[i].second, idx = que[i].first;

            for(int ii = 0; ii < imp_sz; ii++) {
                if(important[ii].i == idx) {
                    important[ii].w = w;
                }
            }

            for(int ii = 1; ii < imp_sz; ii++) {
                if(cmp(important[ii], important[ii - 1])) {
                    swap(important[ii], important[ii - 1]);
                }
            }

            for(int ii = imp_sz - 2; ii >= 0; ii--) {
                if(cmp(important[ii + 1], important[ii])) {
                    swap(important[ii], important[ii + 1]);
                }
            }

            d.init(cnt);
            for(int ii = 0; ii < imp_sz; ii++) {
                int u = get(important[ii].u), v = get(important[ii].v),
                    w = important[ii].w;
                if(!d.connected(u, v)) {
                    answer[i] += w, d.unite(u, v);
                }
            }
        }

        int p = 0, I = 0, J = 0;
        while(I < m && J < imp_sz) {
            if(used[ed[I].i]) {
                I++;
                continue;
            }

            if(used2[important[J].i]) {
                J++;
                continue;
            }

            if(cmp(ed[I], important[J])) {
                nw_li[p++] = ed[I++];
            } else {
                nw_li[p++] = important[J++];
            }
        }

        while(I < m) {
            if(used[ed[I].i]) {
                I++;
                continue;
            }

            nw_li[p++] = ed[I++];
        }

        while(J < imp_sz) {
            if(used2[important[J].i]) {
                J++;
                continue;
            }

            nw_li[p++] = important[J++];
        }

        for(int i = 0; i < m; i++) {
            ed[i] = nw_li[i];
        }

        for(int i = 0; i < m; i++) {
            pos_edge[ed[i].i] = i;
        }
    }

    for(int i = 0; i < q; i++) {
        cout << answer[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation

```python
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

class DSU:
    def __init__(self, n):
        self.par = list(range(n))
        self.sz = [1]*n
    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x
    def unite(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.sz[rx] < self.sz[ry]:
            rx, ry = ry, rx
        self.par[ry] = rx
        self.sz[rx] += self.sz[ry]
        return True
    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    n, m = map(int, input().split())
    edges = []
    for i in range(m):
        u,v,w = map(int, input().split())
        edges.append([u-1, v-1, w, i])
    # sort edges by weight
    edges.sort(key=lambda e: e[2])
    # map from edge_id to its position in edges[]
    pos = [0]*m
    for idx, e in enumerate(edges):
        pos[e[3]] = idx

    t = int(input())
    queries = [tuple(map(int, input().split())) for _ in range(t)]
    # zero-based edge index
    queries = [(e-1, c) for e,c in queries]

    B = 200
    ans = [0]*t

    for st in range(0, t, B):
        en = min(t, st+B) - 1
        # mark edges that will be updated in this block
        will = [False]*m
        for j in range(st, en+1):
            eid, _ = queries[j]
            will[ pos[eid] ] = True

        # 1) baseline MST ignoring those edges
        dsu0 = DSU(n)
        base = 0
        for i, e in enumerate(edges):
            if will[i]: continue
            u,v,w,_ = e
            if dsu0.unite(u,v):
                base += w

        # assign comp-id per connected component
        comp = {}
        cid = 0
        root_id = [0]*n
        for v in range(n):
            r = dsu0.find(v)
            if r not in comp:
                comp[r] = cid
                cid += 1
            root_id[v] = comp[r]

        # 2) pick important edges: those non-updated edges that cross comp boundaries
        dsu1 = DSU(cid)
        imp = []
        for i,e in enumerate(edges):
            if will[i]: continue
            u,v,w,orig = e
            cu, cv = root_id[u], root_id[v]
            if not dsu1.same(cu, cv):
                dsu1.unite(cu, cv)
                imp.append([u, v, w, orig])

        # 3) add the B updated edges (with their current weights)
        for j in range(st, en+1):
            eid, neww = queries[j]
            idx = pos[eid]
            u,v,_,orig = edges[idx]
            imp.append([u, v, neww, orig])

        # sort imp by weight
        imp.sort(key=lambda z: z[2])

        # 4) answer each query in block
        for j in range(st, en+1):
            eid, neww = queries[j]
            # update that edge in imp
            for k in range(len(imp)):
                if imp[k][3] == eid:
                    imp[k][2] = neww
                    # bubble adjust by at most one step each way
                    if k+1<len(imp) and imp[k+1][2]<imp[k][2]:
                        imp[k], imp[k+1] = imp[k+1], imp[k]
                    elif k>0 and imp[k][2]<imp[k-1][2]:
                        imp[k], imp[k-1] = imp[k-1], imp[k]
                    break
            # run small Kruskal on imp
            dsu2 = DSU(cid)
            total = base
            for u,v,w,orig in imp:
                cu, cv = root_id[u], root_id[v]
                if dsu2.unite(cu, cv):
                    total += w
            ans[j] = total

        # 5) rebuild global edges[] with updated weights, then sort
        weight_map = {}
        for i in range(st, en+1):
            eid, neww = queries[i]
            weight_map[eid] = neww
        for idx in range(m):
            u,v,w,eid = edges[idx]
            edges[idx][2] = weight_map.get(eid, w)
        edges.sort(key=lambda e: e[2])
        for idx,e in enumerate(edges):
            pos[e[3]] = idx

    # 5) output
    print("\n".join(map(str,ans)))

if __name__ == "__main__":
    main()
```

Explanation Highlights:
- We group queries into blocks to limit full-graph work to O(m α(m)) per block.
- Within a block, only B edges change; most of the MST can be precomputed (the "baseline" on unchanged edges).
- Contracting baseline components into super-nodes shrinks the problem: only ≲n edges plus B updates need reconsideration.
- Each single-edge update in the block can then be answered by rerunning Kruskal on O(n+B) edges in nearly-linear time.
- Finally, updated edges are merged back into the global sorted array to prepare the next block.
This yields an overall complexity roughly O((t/B)·m α(n) + t·(n+B) α(n) + (t/B)·(m+B)), which is efficient for n,m,t ≤ 4·10^4.
