Jiufeng likes playing table football (shown as the following picture), but he does not know how to play football, so he plans to go to the playground.

Now there are N people(numbered from 1 to N) on the playground preparing for the game. Because they do not know each other and do not have enough experience, so they are easy to make mistakes and difficult to cooperate with. Now Jiufeng knows that there are some gaps between players which cause them making mistakes. As long as training for t minutes in the same team, they will not make mistakes any more. If two players have no gap between them, they will have no chances to make mistakes. The game can only be played when all players in the same teams do not have chances to make mistakes, and there are no more than two teams in total.

Now given all the information about all the participants, Jiufeng wants to know how to allocate players to minimize the team's training time. Please tell Jiufeng how long it takes.

Please note that the number of people can be different between the two teams.

There are multiple test cases, the first line contains a single integer T (1 ≤ T ≤ 3) — the number of test cases.

The first line of each test case contains two integers N and M (1 ≤ N ≤ 2 × , 1 ≤ M ≤ ), indicating the number of people and connections. 

Then followed M lines, each line contains three integers , (1 ≤ ,  ≤ N,  != ) and (1 ≤  ≤ ), indicating that player  and player  need  minutes of training.

For each test case, print the shortest training time for the two teams, also means the shortest waiting time before the start of the game.

1
4 6
1 4 50
2 3 100
1 2 1000
1 3 300
2 4 30
3 4 800

100

For the first sample, Jiufeng can arrange No. 1 and No. 4 in a team, and No. 2 and No. 3 in a team. It only takes 100 minutes for him to train. Here shows the picture: