spider.cpp
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
#define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
#define REP(i,a) for (int i = 0; i < (a); ++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for (int i = (a); i >= (b); --i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
//////////////////////////////////
#define MAXN 2222
#define MAXM 1111111
int N, M;
//vector<int> graph[MAXN], cost[MAXN];
int eA[MAXM], eB[MAXM], eC[MAXM], e[MAXM];
int father[MAXN], rank[MAXN];
int root(int v){
return father[v] == -1? v : father[v] = root(father[v]);
}
int used;
int DFU(int edge){
int a = eA[edge], b = eB[edge], c = eC[edge];
int ca = root(a), cb = root(b);
if(ca == cb) return 0;
if(rank[ca] < rank[cb]) father[ca] = cb;
else if(rank[ca] > rank[cb]) father[cb] = ca;
else{
father[ca] = cb;
rank[cb]++;
}
used++;
return c;
}
bool cmp(int a, int b){
return eC[a] < eC[b];
}
int main() {
while(scanf("%d%d", &N, &M) != EOF){
int m = 0;
REP(i, M){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--; b--;
eA[i] = a;
eB[i] = b;
eC[i] = c;
// graph[a].push_back(b);
// graph[b].push_back(a);
// cost[a].push_back(c);
// cost[b].push_back(c);
e[i] = i;
father[i] = -1;
rank[i] = 0;
if(eC[m] < eC[i]) m = i;
}
eC[m] *= -1;
sort(e, e + M, cmp);
int sum = 0;
used = 0;
REP(i, M) sum += DFU(e[i]);
if(used == N-1) printf("%d\n", sum);
else printf("disconnected\n");
}
return 0;
}