Even number of kids gathered together to play football. There are n kids and they want to divide to two teams, each team having $\frac{n}{2}$ players.

Each kid knows, who he wants to play with and how much he wants to play with every of those kids. Each desire is expressed by a positive integer. Plus, if kid v has a desire equal to d to play with kid u, then u also has a desire equal to d to play with v.

It's not always possible to satisfy all the wishes of kids. The kids thought, that if two kids play in different teams and their desire to play together is very high, then it's not good division to teams. So they want to divide themselves into two teams, so that the highest desire between two players from different teams is as small as possible.

Help them find the minimum highest desire, they can achieve, or say that, you can divide kids into two teams such that if kids want to play together, they are in one team.

Input format

The first line contains an even integer n and an integer m — the number of kids and the number of pairs of kids, who want to play together ($2 \le n \le 1000$; $0 \le m \le 2 \cdot 10^5$).

Next m lines describe pairs of kids, who want to play together. Each of these lines consists of three integers: u, v and d — kids u and v have desire equal to d to play together ($1 \le u, v \le n$; $u \ne v$; $1 \le d \le 10^9$). All m pairs of kids are distinct.

Output format

Output single integer: the smallest possible highest desire kids achieve, after they divide into two teams optimally. If kids can divide into two teams, so that every pair of kids, who want to play together, are in one team, then output 0.