UPGRADE (CSPTST 2022-2023)

#define task "UPGRADE"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
struct dsu
{
    int par[N];
    dsu()
    {
        memset(par, -1, sizeof par);
    }

    int findpar(int v)
    {
        return par[v] < 0 ? v : par[v] = findpar(par[v]);
    }

    bool Merge(int u, int v)
    {
        u = findpar(u);
        v = findpar(v);

        if (u == v)
            return false;

        if (par[u] < par[v])
            swap(u, v);

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

        return true;
    }
} f[500];

int m, n, w, q, id[N];
struct Edge
{
    int u, v, w;
} e[N];

void Read()
{
    cin >> n >> m >> w;

    for (int i = 1; i <= m; ++i)
        cin >> e[id[i] = i].u >> e[i].v >> e[i].w;

    cin >> q;
}

void Solve()
{
    sort(id + 1, id + m + 1, [&](const int &x, const int &y)
         { return e[y].w < e[x].w; });

    ll ans(0);

    for (int i = 1; i <= m; ++i)
        if (f[0].Merge(e[id[i]].u, e[id[i]].v))
        {
            for (int j = e[id[i]].w; j > 0; --j)
                f[j - 1].Merge(e[id[i]].u, e[id[i]].v);

            ans += e[id[i]].w;
        }

    while (q--)
    {
        int x, v;
        cin >> x >> v;

        if (v == 0)
        {
            cout << ans << "\n";
            continue;
        }

        if (f[e[x].w + v - 1].Merge(e[x].u, e[x].v))
        {
            ans += e[x].w + v;

            for (int i = e[x].w + v - 1; i > 0; --i)
                if (!f[i - 1].Merge(e[x].u, e[x].v))
                {
                    ans -= i;
                    break;
                }
        }
        e[x].w += v;

        cout << ans << "\n";
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}