记录编号	123904	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.346 s
提交时间	2014-10-01 07:32:32	内存使用	0.47 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 205
int map[N][N];
int n, m;

inline void floyd(){
	for (int i = 1; i <= n; i ++) map[i][i] = 0;
	for (int k = 1; k <= n; k ++)
		for (int i = 1; i <= n; i ++){
			if (i != k){
				for (int j = 1; j <= n; j ++)
					if (j !=i && j != k){
						map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
					}
			}
		}
}

int main(){
	freopen("hardest.in", "r", stdin);
	freopen("hardest.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T --){
		memset(map, 0x3f, sizeof(map));
		scanf("%d %d", &n, &m);
		int x, y, z;
		for (int i = 1; i <= m; i ++){
			scanf("%d %d %d", &x, &y, &z);
			map[x][y] = min(map[x][y], z);
			map[y][x] = min(map[x][y], z);
		}
		floyd();
		if (map[1][n] != 0x3f3f3f3f)
			printf("%d\n", map[1][n]);
		else printf("-1\n");
	}
	return 0;
}