#include<iostream.h>
#include<conio.h>
#include<stdio.h>

int NodeCount;
char Node[20];
char ddd;
char Graph[20][20];
char Graphs[20][20];
char RuDu[20];
char Checked[20];
char Value[20];
char cho[20];
char sss;
char Locate(char Char)
{
	char Temp;
	for(Temp=0;Temp<NodeCount;Temp++)
		if(Node[Temp]==Char)
			break;
	return Temp;
}

void main()
{
	char Temp1,Temp2;
	int Temp3,Temp4;
	int max,current;
	char Condition=1;
	char min,mintemp,mintemp1;
	clrscr();
	for(Temp2=0;Temp2<20;Temp2++)
		for(Temp1=0;Temp1<20;Temp1++)
			Graph[Temp2][Temp1]=0;
	for(Temp1=0;Temp1<20;Temp1++)
	{
		Checked[Temp1]=0;
		Value[Temp1]=0;
		cho[Temp1]=255;
	}
	cout<<"Input the node count:";
	cin>>NodeCount;
	cout<<"Input the node:";
	for(Temp1=0;Temp1<NodeCount;Temp1++)
		  cin>>Node[Temp1];
	cout<<"Input the link"<<endl;
	Temp1=0;
	while(1)
	{
		cout<<"Input the first node:";
		cin>>Temp1;
		cout<<"Input the second node:";
		cin>>Temp2;
		cout<<"Input the value:";
		cin>>Temp3;
		if(Temp1=='$')
			break;
		Temp1=Locate(Temp1);
		Temp2=Locate(Temp2);
		Graph[Temp1][Temp2]=Temp3;
	}
	for(Temp2=0;Temp2<NodeCount;Temp2++)
	{
		for(Temp1=0;Temp1<NodeCount;Temp1++)
			cout<<(int)Graph[Temp2][Temp1]<<" ";
		cout<<endl;
	}
	for(Temp2=0;Temp2<20;Temp2++)
		for(Temp1=0;Temp1<20;Temp1++)
			Graphs[Temp2][Temp1]=Graph[Temp2][Temp1];

	while(Condition)
	{
		for(Temp1=0;Temp1<NodeCount;Temp1++)
			RuDu[Temp1]=0;
		for(Temp2=0;Temp2<NodeCount;Temp2++)
		{
			Temp3=0;
			for(Temp1=0;Temp1<NodeCount;Temp1++)
				if(Graph[Temp1][Temp2])
					Temp3++;
			RuDu[Temp2]=Temp3;
		}
		Condition=0;
		for(Temp1=0;Temp1<NodeCount;Temp1++)
			if((!RuDu[Temp1])&&(!Checked[Temp1]))
			{
				for(Temp2=0;Temp2<NodeCount;Temp2++)
					Graph[Temp1][Temp2]=0;
				Checked[Temp1]=1;
				max=0;
				for(Temp4=0;Temp4<NodeCount;Temp4++)
					if((Graphs[Temp4][Temp1]>0)&&(max<Value[Temp4]+Graphs[Temp4][Temp1]))
					{
						max=Value[Temp4]+Graphs[Temp4][Temp1];
						current=Temp4;
					}
				cout<<Node[Temp1]<<max<<endl;
				Value[Temp1]=max;
				sss=current;
				ddd=Temp1;
				Condition=1;
			}
	}
	cout<<endl;
	cout<<Node[0]<<"->";
	Temp4=0;
	n1:for(Temp1=0;Temp1<NodeCount;Temp1++)
	{
		if((Graphs[Temp1][sss]==Value[sss]-Value[Temp1])&&(sss!=0))
		{
			cho[Temp4]=sss;
			sss=Temp1;
			Temp4++;
			goto n1;
		}
	}
	for(Temp3=Temp4-1;Temp3>=0;Temp3--)
		cout<<Node[cho[Temp3]]<<"->";
	cout<<Node[ddd];
}