1. Abridged Problem Statement

You are given 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 a single specified edge is updated. After each update, you must report the total weight of the minimum spanning tree (MST) of the graph with the current edge weights. Constraints:
- 2 ≤ n ≤ 40 000, n–1 ≤ m ≤ 40 000
- 1 ≤ t ≤ 40 000
- Edge weights and updates are in [1, 40 000].

2. Detailed Editorial

We need to answer t single-edge-weight updates on an m-edge graph by recomputing the MST cost after each update. Recomputing an MST from scratch in O(m log m) per query would be O(t·m log m) ≈ 10^10, which is too large. Instead, we use an offline sqrt-decomposition over the sequence of updates, processing blocks of B ≈ 200 updates at a time.

Notation:
- Let ed[] be the array of edges kept sorted by current weight.
- Let que[] be the list of t queries, each query being (edge_id, new_weight).
- Maintain pos_edge[] so that pos_edge[edge_id] = the position of that edge in ed[].
- We process queries in blocks of size B. For each block [st…en]:
  1. Mark the set of edge IDs whose weight will change within this block (used[edge_id]).
  2. Build a "baseline" partial MST using only edges not in that set. Two DSUs are used: tmp runs standard Kruskal to detect connectivity, and additional_d records which vertices get unioned. The baseline MST weight is stored in sum.
  3. After the baseline pass, assign super-node IDs via comp_id[]: each distinct root in additional_d becomes one super-node.
  4. Extract "important" edges: for each non-touched edge in ed[], if its two super-node endpoints are not yet connected in a fresh DSU d, unite them and add the edge to important[]. These are at most cnt-1 edges (one per possible merge in the contracted graph). Mark them in used2[edge_id].
  5. Append the touched edges (with their current weights) to important[] and sort important[] by weight.
  6. For each query j in [st…en]:
     a. Update the affected edge's weight in important[].
     b. Re-sort by doing a single forward pass (bubble-up) followed by a single backward pass (bubble-down) over important[], which is sufficient since only one weight changed.
     c. Run a small Kruskal on important[] using DSU d over cnt super-nodes: start from sum and add each edge from important[] that connects two different super-nodes. Store the result in answer[j].
  7. Merge the touched edges back into ed[] sorted order using a two-pointer merge (skipping entries in ed[] with used[edge_id]=1 and skipping entries in important[] with used2[edge_id]=1). Rebuild pos_edge[].

Complexities:
- Blocks: O(t/B)
- Per block:
  • Building baseline MST: O(m α(n))
  • Extracting important edges: O(m α(n))
  • Sorting important[]: O((n + B) log(n + B))
  • Per query: O(n + B) for the bubble passes + O((n + B) α(n)) for the small Kruskal.
Since B is chosen as ≈200, total work fits within the time limit.

3. C++ Solution

```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;
}
```

4. Python Solution

```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) merge back updated edges into edges[]
        weight_map = {}
        for j in range(st, en+1):
            eid, neww = queries[j]
            weight_map[eid] = neww
        for u,v,w,orig in edges:
            w = weight_map.get(orig, w)
            new_edges = []
        for u,v,w,orig in edges:
            new_edges.append([u,v,weight_map.get(orig, w),orig])
        # sort again
        new_edges.sort(key=lambda e: e[2])
        edges = new_edges
        for idx,e in enumerate(edges):
            pos[e[3]] = idx

    # print answers
    print('\n'.join(map(str, ans)))

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

5. Compressed Editorial

Use offline sqrt-decomposition on t updates with block size B. In each block, mark B edges whose weights will change. Build a baseline MST ignoring these B edges (using DSU in O(m α(n))). Compress the graph's connected components into super-nodes. Extract all non-updated edges that still connect different super-nodes — they form at most n–1 edges — and append the B updated edges; sort this small list (size ~n+B). Then for each query in the block, update the one edge's weight in this list (by a pair of bubble passes over the nearly-sorted list) and rerun Kruskal on it with another DSU of size ~n, adding to the baseline sum. Finally, merge the updated edges back into the global sorted edge list for the next block. This yields an overall near-linear solution that handles t, m, n ≤ 40 000 within time.
