记录编号	539886	评测结果	AAAAA
题目名称	1254.最难的任务	最终得分	100
用户昵称	WxjianF019	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2019-08-11 17:10:52	内存使用	13.67 MiB

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
inline int read(){
	int x=0;char c=getchar();
	while(c<'0')c=getchar();
	while(c>='0')x=x*10+c-'0',c=getchar();
	return x;
}
const int maxn=2e2+5;
int n,m;vector<int>e[maxn],v[maxn];
int dis[maxn],bein[maxn];queue<int>q;
void SPFA(){
	q.push(1);dis[1]=0;
	while(!q.empty()){
		int x=q.front();q.pop();bein[x]=false;
		for(int i=0;i<e[x].size();i++){
			int to=e[x][i];
			if(dis[to]>dis[x]+v[x][i]){
				if(!bein[to])q.push(to),bein[to]=true;
				dis[to]=dis[x]+v[x][i];
			}
		}
	}
}
int main(){
	freopen("hardest.in","r",stdin);freopen("hardest.out","w",stdout);
	int t=read();while(t--){
		memset(bein,0,sizeof bein);
		memset(dis,0x3f,sizeof dis);
		while(!q.empty())q.pop();
		n=read(),m=read();
		for(int i=1;i<=n;i++)e[i].clear(),v[i].clear();
		for(int i=0;i<m;i++){
			int x=read(),y=read(),z=read();
			e[x].push_back(y);v[x].push_back(z);
			e[y].push_back(x);v[y].push_back(z);
		}
		SPFA();
		printf("%d\n",dis[n]==0x3f3f3f3f?-1:dis[n]);
	}
	return 0;
}