文理学院程序设计在线练习


Train tour to Tibet

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 9   Accepted Submission(s): 4
Problem Description

After Mr.Bluefly bought his new mobile-phone, he now feels energetic. So he decides to travel to Tibet by train and, in the mean time, to see whether China Mobile’s network coverage is good or not. He feels like to face some challenge so he decides to take “Green Train” (slow train) all the way. But he feels that it is a waste of time to go through a place twice. So he will pay twice the fee for a faster train if he is on the same path for the second time. And here is the question: How to minimize the cost by organizing the path if you are to help him buy the train tickets?(It is not because Mr.Bluefly is mean, but that you will get the rest of the budget if there’s any left :) )

Input

An integer T in the first line, then follows T groups of test data.
In each data group, two integers n and m in the first line indicates that the end point is No.n point and there are m edges. Then m lines, each line contains 3 integers a[i],b[i],c[i] which means there is an undirected-edge between point a[i] and point b[i] with the cost c[i].
(0<=N<=1000,0<=M<=10000,c[i]<=10000)

Output

Each line an integer of the minimum total cost of each test data group.

Sample Input
1
4 5
1 2 10
1 3 14
2 3 2
2 4 14
3 4 10
Sample Output
48
Source

2014市赛