TOURS - Travelling tours

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 should 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

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

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

hide comments
2017-11-26 17:23:39
How to solve this problem? Any idea?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.