/*题目描述：
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路
交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入：
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，
分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
输出：
对每个测试用例，在1行里输出最小的公路总长度。
样例输入：
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
样例输出:
3
5
*/
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define inf 999999
#define M 105
int visit[105];//记录该点是否被访问
int tu[M][M];//零阶矩阵来保存图，值为两点之间的距离
int dist[M];//剩余点到子图的最小距离int main(){int N,n;int a,b,dis;int mins;while(scanf("%d",&N)!=EOF&&N){memset(visit,0,sizeof(visit));//对数组进行初始化memset(tu,inf,sizeof(tu));memset(dist,inf,sizeof(dist));n=N*(N-1)/2;mins=0;for(int i=0;i<n;i++){scanf("%d%d%d",&a,&b,&dis);tu[a][b]=tu[b][a]=dis;}dist[1]=0;//1到1点的距离为0；visit[1]=1;//将1结点作为子图的第一个元素for(int i=2;i<=N;i++)dist[i]=tu[1][i];//余下点中到1点的距离for (int i=1;i<N;i++){//把其余n-1个点放进来int v=1;//给予v一个初值int temp=inf;for(int j=1;j<=N;j++){//查询到子图中最小距离的点if(!visit[j]&&dist[j]<temp&&dist[j]>0){v=j;temp=dist[j];}}visit[v]=1;//将该点加入进去子图if(v!=1)mins+=temp;for(int j=1;j<=N;j++){//更新剩余结点到子图的最小距离if(!visit[j]&&dist[j]>tu[v][j])dist[j]=tu[v][j];}}printf("%d\n",mins);}
return 0;
}