Description：

给一个图，支持修改边权，每次修改完后求最小生成树。

$1\leqslant n\leqslant 50000$

Solution：

对于这种每次操作完回答一些问题的题（ AHOI2013连通图 ， 经典傻逼题 ），可以往分治那里想。

这个题也是分治，但是并不是像线段树分治那样把边拆成 $\log$ 个区间然后用什么数据结构维护，直接说正解。

假设当前分治到了 $[l,r]$ ，那么我们就要考虑怎么样把这个区间操作的复杂度降低到只与 $r-l+1$ 有关，发现在这个图中有一些边是一定在最后的最小生成树中的，有些边是一定不在的，也就是说区间内边的变化不能影响这些边的情况，那么我们就可以试着在这个区间就把这些边处理掉。（刚开始点和边为 $(n,m)$ ，区间长为 $k$ ）。

Reduction操作：用来清除无用边，减少边的数量。

首先把所有在这个区间中会修改的边边权赋成 $\infty$ ，然后做最小生成树，这时没有在最小生成树中的边一定不会在最小生成树中，可以把它们删掉，不再传递给儿子节点， $(n,m)\to(n,n-1+k)$ 。

Contraction操作：用来添加必须边并缩点，减少点的数量。

首先把所有在这个区间中的会修改的边边权赋成 $-\infty$ ，然后做最小生成树，这时还被加到 $MST$ 中的边在这个区间中一定会被加到最小生成树中，那就现在就把他们加进去，并用并查集缩点， $(n,m)\to(k+1,m)$ 。

然后我们在分治区间做：Reduction $\to$ Contraction $\to$ Reduction。

点和边的数量变化为 $(n,m)\to(n,n-1+k)\to(k+1,n-1+k)\to(k+1,2k)$ 。

于是我们成功地把问题的规模缩小到了只与 $k$ 有关，就可以直接做了，时间复杂度 $O(n\log^2n)$ 。

注意维护连通性要用带撤销操作的并查集，不可路径压缩。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,p;

#define MAXN 50010

struct UFS

{

	int f[MAXN],rnk[MAXN];

	int find(int x){return (x == f[x] ? x : find(f[x]));}

	int s[MAXN << 1],top;

	void init()

	{

		for(int i = 1;i <= n;++i)f[i] = i;

		for(int i = 1;i <= n;++i)rnk[i] = 1;

		top = 0;

		return;

	}

	bool gather(int a,int b)

	{

		return (find(a) == find(b));

	}

	void merge(int a,int b)

	{

		int p = find(a),q = find(b);

		if(rnk[p] > rnk[q])swap(p,q);

		s[++top] = p;f[p] = q;

		if(rnk[p] == rnk[q])

		{

			++rnk[q];

			s[++top] = -q;

		}

		return;

	}

	void reset(int pos)

	{

		while(top > pos)

		{

			int v = s[top];--top;

			if(v > 0)f[v] = v;

			else --rnk[-v];

		}

		return;

	}

}s;

struct edges

{

	int u,v,w;

}es[MAXN];

int e[MAXN],tmp[MAXN];

bool cmp_w(int a,int b){return es[a].w < es[b].w;}

bool vis[MAXN];

struct query

{

	int id,val;

}q[MAXN];

long long ans[MAXN];

bool nouse[MAXN];

void reduction(int &m)

{

	int top = s.top;

	for(int i = 1;i <= m;++i)

	{

		if(vis[e[i]])continue;

		if(s.gather(es[e[i]].u,es[e[i]].v))

		{

			nouse[e[i]] = true;

		}

		else s.merge(es[e[i]].u,es[e[i]].v);

	}

	int ptr1 = 0,ptr2 = 0;

	for(int i = 1;i <= m;++i)

	{

		if(!nouse[e[i]])e[++ptr1] = e[i];

		else tmp[++ptr2] = e[i];

	}

	m = ptr1;

	for(int i = 1;i <= ptr2;++i)e[++ptr1] = tmp[i];

	for(int i = 1;i <= ptr1;++i)nouse[e[i]] = false;

	s.reset(top);

	return;

}

long long contraction(int &m)

{

	int top = s.top;

	for(int i = 1;i <= m;++i)

	{

		if(vis[e[i]] && !s.gather(es[e[i]].u,es[e[i]].v))

		{

			s.merge(es[e[i]].u,es[e[i]].v);

		}

	}

	long long res = 0;

	for(int i = 1;i <= m;++i)

	{

		if(vis[e[i]])continue;

		if(!s.gather(es[e[i]].u,es[e[i]].v))

		{

			s.merge(es[e[i]].u,es[e[i]].v);

			res += es[e[i]].w;

			nouse[e[i]] = true;

		}

	}

	s.reset(top);

	for(int i = 1;i <= m;++i)

	{

		if(!vis[e[i]] && nouse[e[i]])s.merge(es[e[i]].u,es[e[i]].v);

	}

	int ptr1 = 0,ptr2 = 0;

	for(int i = 1;i <= m;++i)

	{

		if(!nouse[e[i]])e[++ptr1] = e[i];

		else tmp[++ptr2] = e[i];

	}

	m = ptr1;

	for(int i = 1;i <= ptr2;++i)e[++ptr1] = tmp[i];

	for(int i = 1;i <= ptr1;++i)nouse[e[i]] = false;

	return res;

}

void solve(int l,int r,int m)

{

	for(int i = l;i <= r;++i)vis[q[i].id] = true;

	int st = s.top;

	if(l == r)es[q[l].id].w = q[l].val;

	sort(e + 1,e + 1 + m,cmp_w);

	reduction(m);

	long long val = contraction(m);

	reduction(m);

	for(int i = l;i <= r;++i)ans[i] += val;

	for(int i = l;i <= r;++i)vis[q[i].id] = false;

	if(l == r)

	{

		for(int i = 1;i <= m;++i)

		{

			if(!s.gather(es[e[i]].u,es[e[i]].v))

			{

				s.merge(es[e[i]].u,es[e[i]].v);

				ans[l] += es[e[i]].w;

			}

		}

	}

	else

	{

		int mid = ((l + r) >> 1);

		solve(l,mid,m);solve(mid + 1,r,m);

	}

	s.reset(st);

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&p);

	for(int i = 1;i <= m;++i)scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].w);

	for(int i = 1;i <= m;++i)e[i] = i;

	for(int i = 1;i <= p;++i)scanf("%d%d",&q[i].id,&q[i].val);

	s.init();

	solve(1,p,m);

	for(int i = 1;i <= p;++i)printf("%lld\n",ans[i]);

	return 0;

}