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;
}