K. Chess Game
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Xiao Ming is a little girl who likes eating cucumbers.

She enjoys playing chess against herself, acting as both the black and white sides simultaneously.

The game is played on an undirected graph $$$G$$$ with $$$n$$$ nodes, containing $$$m$$$ undirected edges. The $$$i$$$-th edge connects nodes $$$u_i$$$ and $$$v_i$$$ with a length of $$$l_i$$$. It is guaranteed that the graph contains no self-loops but may have multiple edges between the same pair of nodes.

In each move, Xiao Ming can choose either side and place a chess piece of the corresponding color on any unoccupied node. After $$$n$$$ rounds, the game ends.

Black and white represent yin and yang, and Xiao Ming wishes to maintain their balance. Therefore, she wants to ensure that no two chess pieces of the same color are placed too close to each other on the graph. Specifically, we consider a simple path $$$p_1,p_2\ldots p_k$$$ that satisfies:

  1. $$$k \ge 2$$$
  2. $$$p_1,p_2\ldots p_k$$$ are all distinct.
  3. Nodes $$$p_1$$$ and $$$p_k$$$ are occupied by chess pieces of the same color.

Xiao Ming defines the balance degree $$$d$$$ of the game as the minimum path length among all such paths that meet the above conditions. If no such path exists, the balance degree is defined as positive infinity.

Please help Xiao Ming plan the game to maximize the balance degree $$$d$$$.

Input

The first line contains two integers $$$n,m$$$ ($$$1 \le n \le 5 \times 10^5$$$, $$$0 \le m \le 5 \times 10^5$$$).

The next $$$m$$$ lines each contain three integers $$$u_i,v_i,l_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$1 \le l_i \le 10^8$$$, $$$u_i \ne v_i$$$).

Note that the input size for this problem is very large, so please use fast input methods.

Output

Output a single integer representing the maximum possible balance degree $$$d$$$ of the game. If the answer is infinity, output $$$-1$$$ instead.

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

One possible optimal arrangement is as follows:

Xiao Ming places black pieces on nodes $$$1,4,3,5$$$ and a white piece on node $$$2$$$. Then, one of the shortest valid simple paths is $$$1-5$$$ with a length of 4.

It can be shown that no better solution exists.