Cod sursă (job #721260)

#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(x) (ll)x.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>;
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]);}}}



//Soltan Cristian
using namespace std;
 
ifstream in("zapada.in");
ofstream out("zapada.out");
 
const int NMAX = 1e4;
const int MMAX = 1e5;
const int DIM = 150000;
 
struct Edge {
  short int from;
  short int to;
  int cost;
 
  bool operator< (Edge other) const {
    return cost < other.cost;
  }
};
 
short int n, k, no;
int pos = DIM - 1;
int m, maxx;
int res;
short int sef[1 + NMAX];
char buff[DIM];
 
Edge v[1 + MMAX];
 
short int get_sef(short int el) {
  if(sef[el] == 0)
    return el;
  else {
    sef[el] = get_sef(sef[el]);
    return sef[el];
  }
}
 
void apm() {
  res = 0;
  no = 0;
 
  //for(short int i = 1; i <= n; i++)
    //sef[i] = i;
  memset(sef, 0, sizeof(sef));
 
  for(int i = 1; i <= m && no <= n - 1; i++) {
    short int bx = get_sef(v[i].from);
    short int by = get_sef(v[i].to);
 
    if(bx != by) {
      sef[bx] = by;
      v[++no] = v[i];
      res += v[i].cost;
      maxx = max(maxx, v[i].cost);
    }
  }
 
  m = no;
  out << res << '\n';
}
 
int read() {
  int x = 0;
  while(!isdigit(buff[pos])) {
    if(++pos == DIM) {
      in.read(buff, DIM);
      pos = 0;
    }
  }
 
  while(isdigit(buff[pos])) {
    x = x * 10 + (buff[pos] -'0');
    if(++pos == DIM) {
      in.read(buff, DIM);
      pos = 0;
    }
  }
 
  return x;
}
 
int main()
{
  //in >> n >> m >> k;
  n = read();
  m = read();
  k = read();
 
  for(int i = 1; i <= m; i++) {
    //in >> v[i].from >> v[i].to >> v[i].cost;
    v[i].from = read();
    v[i].to = read();
    v[i].cost = read();
  }
  sort(v + 1, v + m + 1);
 
  apm();
 
  for(short int w = 1; w <= k; w++) {
    m++;
    //in >> v[m].from >> v[m].to >> v[m].cost;
    v[m].from = read();
    v[m].to = read();
    v[m].cost = read();
    if(maxx < v[m].cost) {
      out << res << '\n';
      continue;
    }
 
    for(int i = m - 1; i >= 1; i--) {
      if(v[i + 1].cost < v[i].cost)
        swap(v[i], v[i + 1]);
      else
        break;
    }
    apm();
  }
 
  in.close();
  out.close();
  return 0;
}