1021:暑期旅行

Time/Memory Limit:1000 MS/32768 K
Submitted: 224 Accepted: 47

 Problem Description

暑假快到了,Mirons想去旅行,他正在计划着.在选定旅行目的地后,接下来就是要选择路线了.Mirons是从A市出发的,他想经过旅行后又回到A市.由于Mirons还是个学生,他并没有很多钱,所以他想找一条最省钱的旅行路线.并且每个城市Mirons只打算去一次.

 Input

第一行是一个正整数t,表示有t组测试数据.接下来每组测试数据的第一行是一个整数n(0<n<=10)和m,n表示Mirons要旅行的n座城市,编号从1~n,其中A市的编号都是1.接下来有m行,每行有三个整数u,v,c(1<=u,v<=n,0<=c<=1000),意思是u市与v市之间旅行要花费c.题目保证所有旅行地会是连通的.

 Output

输出最小的旅行花费.

 Sample Input

1
4 6
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
2 4 6

 Sample Output

10

 Author

jwt

 Recommend

zh