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:
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$$$.
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 a single integer representing the maximum possible balance degree $$$d$$$ of the game. If the answer is infinity, output $$$-1$$$ instead.
5 61 5 41 3 44 1 52 1 22 5 41 2 1
4
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.
