UVA 11733 Airports

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])
#define inone(x) scanf("%d",&x)
#define intwo(x,y) scanf("%d%d",&x,&y)
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)
const int N = 1e5+ 10;
const int mod = 1e9 + 7;
int T, n, m, d, cas = 0;
int x[N], y[N], z[N], a[N], fa[N];

int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }

int main()
{
  for (inone(T); T; T--)
  {
    inthr(n, m, d);
    rep(i, 1, n) fa[i] = i;
    rep(i, 1, m) inthr(x[i], y[i], z[i]), a[i] = i;
    sort(a + 1, a + m + 1, [](int u, int v) {return z[u] < z[v]; });
    int cnt = n, sum = 0;
    rep(i, 1, m)
    {
      if (z[a[i]] >= d) break;
      int fx = get(x[a[i]]), fy = get(y[a[i]]);
      if (fx == fy) continue;
      fa[fx] = fy; cnt--; sum += z[a[i]];
    }
    printf("Case #%d: %d %d\n", ++cas, sum + cnt*d, cnt);
  } 
  return 0;
}