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) cout << ">>> " << #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;
///////////////////////////////////////////////////////////////////////////
const int MAX = 2007;
int N, M;
int parent[MAX];
int get(int n)
{
return parent[n] = (n == parent[n] ? n : get(parent[n]));
}
bool joined(int a, int b)
{
a = get(a);
b = get(b);
return a == b;
}
void join(int a, int b)
{
a = get(a);
b = get(b);
parent[a] = b;
}
struct Edge
{
int a, b, c;
bool operator<(const Edge & e) const { return c < e.c; }
} edges[1000000];
int main()
{
while (scanf("%d%d", &N, &M) == 2)
{
REP(i, N) parent[i] = i;
REP(i, M)
{
scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].c);
--edges[i].a;
--edges[i].b;
}
sort(edges, edges+M);
int used = 0, result = 0;
if (M)
{
result -= edges[M-1].c;
join(edges[M-1].a, edges[M-1].b);
++used;
}
REP(i, M-1)
{
if (!joined(edges[i].a, edges[i].b))
{
join(edges[i].a, edges[i].b);
result += edges[i].c;
++used;
}
}
if (used != N-1)
printf("disconnected\n");
else
printf("%d\n", result);
}
return 0;
}