记录编号	126264	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	chs	是否通过	通过
代码语言	C++	运行时间	0.425 s
提交时间	2014-10-11 21:01:35	内存使用	0.31 MiB

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int maxx=9999999;
const int maxn=201;
int T;
void core()
{
	int n,m;
	int i,j,k;
	int leng[maxn][maxn];
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i==j) continue;
			leng[i][j]=maxx;
		}
	}
	for(i=1;i<=m;i++)
	{
		int t1,t2,temp;
		cin>>t1>>t2>>temp;
		leng[t1][t2]=min(leng[t1][t2],temp);
		leng[t2][t1]=min(leng[t2][t1],temp);
	}
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				leng[i][j]=min(leng[i][j],leng[i][k]+leng[k][j]);
	if(leng[1][n]!=maxx) cout<<leng[1][n]<<endl;
	else cout<<-1<<endl;
}
int main()
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	cin>>T;
	while(T>0)
	{
		core();
		T--;
	}
	return 0;
}