#include<iostream>
const int INFINITY=10000000;
using namespace std;
typedef char *VEXS;
typedef struct
{
	VEXS vexs;
	int vexnum;
}MGraph;
typedef bool ***PathMatrix;
typedef int **DistanceMatrix;

int main()
{
	MGraph G;
	int n;
	int v,w,u,i; 
	int a,b,distance;
	cout<<"請輸入村莊數目：";
	cin>>n;
	G.vexnum=n;
	VEXS vexs;
	vexs=(char*)malloc(n*sizeof(char));
	for(v=0;v<n;v++)
	{
		vexs[v]=char(v+97);
	}
	DistanceMatrix D;
	D=(DistanceMatrix)malloc(n*sizeof(int*));
	for(v=0;v<n;v++)
	{
		D[v]=(int*)malloc(n*sizeof(int));
	}
	for(v=0;v<n;v++)
	{
		for(w=0;w<n;w++)
		{
			if(v==w) D[v][w]=0;
			else  D[v][w]=INFINITY;
		}
	}
	for(v=0;v<n*(n-1);v++)
	{
		cout<<"請輸入兩個不同村莊的距離:"<<endl;
		cout<<"村莊首:";
		cin>>a;
		cout<<"村莊尾:";
		cin>>b;
		if(a==b)break;
		cout<<"距離:";
		cin>>distance;
		D[a-1][b-1]=distance;
	}
	PathMatrix P;
	P=(PathMatrix)malloc(n*sizeof(bool**));
	for(v=0;v<n;v++)
	{
		P[v]=(bool**)malloc(n*sizeof(bool*));
	}
   for(v=0;v<n;v++)
	{
		for(w=0;w<n;w++)
		{
			P[v][w]=(bool*)malloc(n*sizeof(bool));
		}
	}
    for(v=0;v<n;v++)
	{
		for(w=0;w<n;w++)
		{
			for(u=0;u<n;u++) P[v][w][u]=false;
			if(D[v][w]<INFINITY)
			{
				P[v][w][v]=true;
                P[v][w][w]=true;
			}
		}
	}
	for(u=0;u<n;u++)
		for(v=0;v<n;v++)
			for(w=0;w<n;w++)
				if(D[v][u]+D[u][w]<D[v][w])
				{
					D[v][w]=D[v][u]+D[u][w];
					for(i=0;i<n;++i)
						P[v][w][i]=P[v][u][i]||P[u][w][i];
				}

	

    for(v=0;v<n;v++)
	{
		for(w=0;w<n;w++)
		{
			if(D[v][w]!=INFINITY)
			cout<<"村莊"<<v+1<<"到村莊"<<w+1<<"的最短距離是"<<D[v][w]<<endl;
		}
	}
	
	return 0;
}