Cod sursă (job #676006)

#include <bits/stdc++.h>
#define N 10005
#define pb push_back

using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

int n, m, k, cost;
vector<int>t;
struct edge {
	int x, y, c;
	bool operator <(const edge A) const {
		return c < A.c;
	}
}g[100005];
void read() {
	fin >> n >> m >> k;
	for (int i = 1; i <= m; ++i)
		fin >> g[i].x >> g[i].y >> g[i].c;
}
int Find(int x) {
	int root = x, y;
	while (t[root])
		root = t[root];
	while (x != root) {
		y = t[x];
		t[x] = root;
		x = y;
	}
	return root;
}
void Union(int x, int y) {
	t[y] = x;
}
void Kruskal() {
	sort(g + 1, g + m + 1);
	for (int i = 1; i <= m; ++i) {
		int r1 = Find(g[i].x), r2 = Find(g[i].y);
		if (r1 != r2) {
			Union(r1, r2);
			cost += g[i].c;
		}
	}
}
void solve() {
	int x, y, c;
	t.resize(n + 5);
	Kruskal();
	fout << cost << "\n";
	for (int i = 1; i <= k; ++i) {
		m++;
		fin >> g[m].x >> g[m].y >> g[m].c;
		cost = 0;
		t.clear();
		t.resize(n + 5);
		Kruskal();
		fout << cost << "\n";
	}
}
int main() {
	read();
	solve();
	return 0;
}