#include <iostream.h>

//求多短路的最短路徑，用動態規劃法
/*
輸入
10 18
0 1 4
0 2 2
0 3 3
1 4 9
1 5 8
2 4 6
2 5 7
2 6 8
3 5 4
3 6 7
4 7 5
4 8 6
5 7 8
5 8 6
6 7 6
6 8 5
7 9 7
8 9 3

輸出
0->3->5->8->9
*/
#define INFI 1000
int c[15][15];//路徑長度
int cost[15];
int path[15];//在最短路徑上，每個點的后繼

void search(int n)
{
	int i,j,minnum;
	for(i=0;i<n;i++)
		cost[i]=INFI;
	cost[n-1]=0;
	for(i=n-2;i>=0;i--)
	{
		for(j=n-1;j>i;j--)
		{
			if(cost[i]>c[i][j]+cost[j]) 
			{
				cost[i]=c[i][j]+cost[j];//修改當前最短路徑的大小
				minnum=j;
			}
		}
		path[i]=minnum;//記下在最短路徑上，該點的后繼
	}
}

void print(int n,int start)
{
	int next=start;
	do
	{
		cout<<next<<"->";
		next=path[next];//求該點的后繼
	}while(next!=n-1);
	cout<<next<<endl;
}
int main()
{
	int num,pnum,i,j,ta,tb,tc;
	cout<<"幾個點,幾條路？"<<endl;
	cin>>num>>pnum;
	for(i=0;i<num;i++)
		for(j=0;j<num;j++)
			c[i][j]=INFI;
	for(i=0;i<pnum;i++)
	{
		cin>>ta>>tb>>tc;
		c[ta][tb]=tc;
	}
	search(num);
	cout<<"點0到終點的最短路徑為：";
	print(num,0);
	return 0;
}