Cod sursă (job #721246)

#include <bits/stdc++.h>
//Soltan Cristian
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
#define Y cout << "YES" << '\n'
#define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
using ml = map<ll, ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pss = pair<string, string>;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T>void print(T n, T m, vector<vector<T>> &dp){fri(0, n){ct('\n');frj(0, m){ct(setw(5));cts(dp[i][j]);}}}
 
 #include <stdio.h>
#include <ctype.h>

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
 
string __fname = "zapada"; 
// ifstream in (__fname + ".in"); 
ofstream out (__fname + ".out");
// #define cin in 
#define cout out
 
vector<int> parent;
vi ranc;
 
void makeSet(int v){
    parent[v] = v;
    ranc[v] = 0;
}
 
int findSet(int v){
    if(v == parent[v]){
        return v;
    }
    return parent[v] = findSet(parent[v]);
}
 
void unionSets(int a, int b){
    a = findSet(a);
    b = findSet(b);
    if(a != b){
        if(ranc[a] < ranc[b]){
            swap(a, b);
        }
        parent[b] = a;
        if(ranc[a] == ranc[b]){
            ranc[a]++;
        }
    }
}
 
 
struct Edge{
    int u, v, cost;
    bool operator<(Edge const& other) {
        return cost < other.cost; // Pentru sortare.
    }
};
 
void solve(){
    InParser fin("zapada.in");
    int n, m, k;
    fin >> n >> m >> k;
    vector<Edge> a;
    ranc.resize(n + 1);
    parent.resize(n + 1);
    fri(0, m){
        int q, p, o;
        fin >> q >> p >> o;
        Edge e = {q, p, o};
        a.push_back(e);
    }
    fri(0, n + 1){
        makeSet(i);
    }
    vector<Edge> ans;
    int rs = 0;
    sort(all(a));
    for(Edge e: a){
        if(findSet(e.u) != findSet(e.v)){
            rs += e.cost;
            unionSets(e.u, e.v);
        }
    }
    ctn(rs);
    rs = 0;
    fri(0, k){
        int q, p, o;
        fin >> q >> p >> o;
        Edge e = {q, p, o};
        a.push_back(e);
        sort(all(a));
        for(Edge e: a){
            if(findSet(e.u) != findSet(e.v)){
                rs += e.cost;
                unionSets(e.u, e.v);
            }
        }
        ctn(rs);
        rs = 0;
    }
 
}
 
 
  
int main()
{   
    // ios_base::sync_with_stdio(0); cin.tie(0); ct(fixed); ct(setprecision(1));
    // int t;
    // cin >> t;
    // while(t--)
        solve();
}