TOURS - Travelling tours

no tags 

In Hanoi, there are N beauty-spots (2 <= N <= 200), connected by M one-way streets. The length of each street does not exceed 10000. You are the director of a travel agency, and you want to create some tours around the city which satisfy the following conditions:

  • Each of the N beauty-spots belongs to exactly one tour.
  • Each tour is a cycle which consists of at least 2 places and visits each place once (except for the place we start from which is visited twice).
  • The total length of all the streets we use is minimal.

Input

The first line of input contains the number of testcases t (t <= 15). The first line of each testcase contains the numbers N, M. The next M lines contain three integers U V W which mean that there is one street from U to V of length W.

Output

For each test case you shold output the minimal total length of all tours.

Example

Input:
2
6 9
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
5 8
1 2 4
2 1 7
1 3 10
3 2 10
3 4 10
4 5 10
5 3 10
5 4 3

Output:
42
40

Detailed explanation:
Test 1:
  Tour #1:  1 - 2 - 3 - 1  --> Length = 20
  Tour #2:  6 - 5 - 4 - 6  --> Length = 22

Test 2:
  Tour #1:  1 - 3 - 2 - 1  --> Length = 27
  Tour #2:  5 - 4 - 5      --> Length = 13


hide comments
severussnape0x: 2017-11-26 17:23:39

How to solve this problem? Any idea?


Added by:Lê Đôn Khuê
Date:2005-06-25
Time limit:0.876s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:2nd round VOI 2004