Invitation Cards

In the age of television, not many people attend theater performances. The Antique Comedians of Malidinesia are aware of this fact. They want to promote theater and, above all, Antique Comedies, so they have printed invitation cards containing all the necessary information and the programme. Many students were hired to hand out these invitations. Each student volunteer is assigned exactly one bus stop, stays there the whole day, and gives an invitation to every person travelling by bus.

The transport system is very special: all lines are one-way and connect exactly two stops. Buses leave their originating stop every half hour and, after reaching the destination, return empty to the originating stop to wait for the next departure. The fare for travelling between two stops is fixed and is paid on the spot when boarding. The lines are planned so that every round trip (a journey that starts and ends at the same stop) passes through a Central Checkpoint Stop (CCS), where every passenger must undergo a thorough check.

Every volunteer leaves the CCS each morning and travels to one predetermined stop to hand out invitations. There are as many volunteers as there are stops, one volunteer per stop. At the end of the day, every volunteer travels back to the CCS. Write a program that minimizes the total amount of money paid each day for the volunteers' transport.

The input consists of several test cases. The first line contains a single positive integer N, the number of test cases. The test cases follow.

Each test case begins with a line containing two integers P and Q (1 <= P, Q <= 1000000). P is the number of stops, including the CCS, and Q is the number of bus lines. The next Q lines each describe one bus line with exactly three integers: the originating stop, the destination stop, and the fare. The CCS is stop number 1. Every fare is a positive integer, and the sum of all fares is smaller than 1000000000. You may assume that it is always possible to travel from any stop to any other stop.

For each test case, print a single line containing the minimum total amount of money that must be paid each day for the volunteers' transport.