spider.cpp

#include <stdio.h>
#include <string.h>
#include <list>
 
using namespace std;
 
class node
{
  public:
  	int itr;
  	list<node*> links;
};
 
node array[2000];
bool barray[2000];
 
void trace(node * first)
{
	if (barray[first->itr])
		return;
	barray[first->itr] = true;
	for (list<node*> ::iterator itr = first->links.begin(); itr != first->links.end(); itr++)
		trace(*itr);
}
 
int main()
{
	int nodes, links;
	for (int i = 0; i < 2000; i++)
		array[i].itr = i;
	while (scanf("%d%d",&nodes, &links) == 2)
	{
		int maxlength = 0;
		int totallength = 0;
		bool disc = false;
		for (int i = 0; i < nodes; i++)
			array[i].links.clear();
		memset(barray, 0, sizeof(barray));
		for (int i = 0; i < links; i++)
		{
			int node1, node2, length;
			scanf("%d%d%d",&node1,&node2,&length);
			if (length > maxlength)
				maxlength = length;
			totallength += length;
			node1--;
			node2--;
 
			array[node1].links.insert(array[node1].links.end(), & array[node2]);
			array[node2].links.insert(array[node2].links.end(), & array[node1]);
		}
		trace(array);
		for (int i = 0; i < nodes; i++)
			if (!barray[i])
			{
				disc = true;
				break;
			}
		if (disc)
		{
			printf("disconnected\n");
			continue;
		}
		printf("%d\n", maxlength * 3 - totallength);
 
	}
	return 0;
}