D. La Pachanga
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You want to organize a soccer match among $$$n$$$ players. You need to separate the players into two teams, and all players have agreed that they do not care about the number of players in each team. However, you know that there are people who cannot even stand to see each other, let alone play on the same team. In fact, you know that $$$m$$$ distinct pairs of players hate each other a certain amount $$$h$$$ (measured in phobios, the usual unit of hate). With this information, you must find the minimum number $$$k \geq 0$$$ such that two distinct teams can be formed where the hate between any two people in the same team is less than or equal to $$$k$$$.

Input

The input consists of multiple cases. The first line will contain a natural number $$$t$$$, the number of cases.

For each case:

- The first line will contain two integers $$$n, m$$$, the number of players, and the number of pairs that hate each other.

- The following $$$m$$$ lines will contain three integers $$$u_k, v_k, h_k$$$, the two players and how much they hate each other. No two pairs $$$u_k$$$ and $$$v_k$$$ will be repeated.

Output

The output should be a natural number for each case, the minimum number $$$k \geq 0$$$ such that two distinct teams can be formed where the hate between any two people in the same team is less than or equal to $$$k$$$.

Scoring

$$$1 \leq t$$$

$$$1 \leq u_k, v_k \leq n, \, u_k \neq v_k$$$

32 points: $$$2 \leq n \leq 2000$$$, $$$0 \leq m \leq 2000$$$, $$$1 \leq h_k \leq 2000$$$

17 points: $$$2 \leq n \leq 2000$$$, $$$0 \leq m \leq 2000$$$, $$$1 \leq h_k \leq 10^9$$$

51 points: $$$2 \leq n \leq 200000$$$, $$$0 \leq m \leq 200000$$$, $$$1 \leq h_k \leq 10^9$$$

Example
Input
2
3 3
1 2 3
2 3 2
1 3 1
4 6
1 2 5
1 3 4
1 4 4
2 3 6
2 4 7
3 4 2
Output
1
4