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 test cases 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