PROGRAMMING:Jiufeng's Football Team
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.
![ QQ picture 2020092095818. PNG] (~ / c36cacae-1092-4746-a7d4-86d8c9763c7a. PNG)
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.**
### Input Specification:
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$$ × $$ 10^4$$, $$1$$ ≤ $$M$$ ≤ $$10^5$$), indicating the number of people and connections.
Then followed $$M$$ lines, each line contains three integers $$a_ i$$, $$b_ i$$(1 ≤ $$a_ i$$, $$b_ i$$ ≤ N, $$a_ i$$ != $$ b_ i$$) and $$t_ i$$(1 ≤ $$t_ i$$ ≤ $$10^9$$), indicating that player $$a_ i$$ and player $$b_ i$$ need $$t_ i$$ minutes of training.
### Output Specification:
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.
### Sample Input：
```in
one
4 6
1 4 50
2 3 100
1 2 1000
1 3 300
2 4 30
3 4 800
```
### Sample Output:
```out
one hundred
```
### Hint:
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:
![ Example. PNG] (~ / 6099a4da-73cd-4661-8426-d24d84538651. PNG)
answer：If there is no answer, please comment
![ QQ picture 2020092095818. PNG] (~ / c36cacae-1092-4746-a7d4-86d8c9763c7a. PNG)
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.**
### Input Specification:
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$$ × $$ 10^4$$, $$1$$ ≤ $$M$$ ≤ $$10^5$$), indicating the number of people and connections.
Then followed $$M$$ lines, each line contains three integers $$a_ i$$, $$b_ i$$(1 ≤ $$a_ i$$, $$b_ i$$ ≤ N, $$a_ i$$ != $$ b_ i$$) and $$t_ i$$(1 ≤ $$t_ i$$ ≤ $$10^9$$), indicating that player $$a_ i$$ and player $$b_ i$$ need $$t_ i$$ minutes of training.
### Output Specification:
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.
### Sample Input：
```in
one
4 6
1 4 50
2 3 100
1 2 1000
1 3 300
2 4 30
3 4 800
```
### Sample Output:
```out
one hundred
```
### Hint:
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:
![ Example. PNG] (~ / 6099a4da-73cd-4661-8426-d24d84538651. PNG)
answer：If there is no answer, please comment