spider.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct edge {
	int u, v, l;
	bool operator<(const edge & rhs) const
	{ return l < rhs.l; }
};
 
vector<int> UF;
vector<int> CS;
 
int find_set(int n) {
	if (n != UF[n])
		UF[n] = find_set(UF[n]);
	return UF[n];
}
bool connected(int u, int v)
{
	return (find_set(u) == find_set(v));
}
void connect(int u, int v)
{
	UF[u] = UF[v];
	CS[u] = CS[v] = CS[u] + CS[v];
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	int N, M;
	while (cin >> N) {
		cin >> M;
		vector<edge> E (M);
		UF = vector<int> (N+1);
		CS = vector<int> (N+1);
		long netl = 0;
 
		// UF
		for (int i = 0; i <= N; ++i) {
			UF[i] = i;
			CS[i] = 1;
		}
 
		// load and sort
		for (int i = 0; i < M; ++i) {
			edge e;
			cin >> e.u >> e.v >> e.l;
			E[i] = e;
		}
		sort (E.begin(), E.end());
 
		// connect longest
		edge longest = E.back();
		netl -= longest.l;
		connect(longest.u, longest.v);
		E.pop_back(); --M;
 
		bool all = false; int ei = 0;
		while (ei < M && !all) {
			edge e = E[ei];
			if (!connected(e.u, e.v)) {
				connect(e.u, e.v);
				netl += e.l;
				if (CS[e.u] == N)
					all = true;
			}
			++ei;
		}
 
		if (all)	cout << netl << '\n';
		else		cout << "disconnected\n";
	}
	return 0;
}