0189-Convenient Location

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0189
ワーシャルフロイトのアルゴリズム
面倒なのは町の個数が決まっていないことかな。

#define INF 999999
#define MAX_V 20
int V;
int d[MAX_V][MAX_V];
int MAP[20];
int MAPcount=0;
void warshall_floyd(){
	for(int k=0;k<V;k++){
		for(int i=0;i<V;i++){
			for(int j=0;j<V;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}
int MAPCheck(int a){
	for(int i=0;i<MAPcount;i++){
		if(MAP[i]==a) return i;
	}
	return -1;
}
int main(int argc,char *argv[]){
	int n;
	int a,b,c;
	int mn,md;
	for(;;){
		for(int i=0;i<MAX_V;i++){
			for(int j=0;j<MAX_V;j++){
				if(i==j) d[i][j]=0; else d[i][j]=INF;
			}
		}
		for(int i=0;i<20;i++) MAP[i]=0;
		MAPcount=0;
		scanf("%d",&n);if(!n) return 0;
		for(int i=0;i<n;i++){
			scanf("%d %d %d",&a,&b,&c);
			if(MAPCheck(a)==-1) MAP[MAPcount++]=a;
			if(MAPCheck(b)==-1) MAP[MAPcount++]=b;
			d[MAPCheck(a)][MAPCheck(b)]=c;
			d[MAPCheck(b)][MAPCheck(a)]=c;
		}
		V=MAPcount;
		warshall_floyd();
		mn=INT_MAX;md=INT_MAX;
		for(int i=0;i<V;i++){
			c=0;
			for(int j=0;j<V;j++){
				c+=d[i][j];
			}
			if(c<md||(c==md&&MAP[i]<mn)){
				md=c;mn=MAP[i];
			}
		}
		printf("%d %d\n",mn,md);
		fflush(stdout);
	}
	return 0;
}