Problem Statement

There is a simple connected undirected graph with $N$ vertices numbered $1$ to $N$. The graph has $M$ weighted edges, and the $i$-th edge connects vertices $A_i$ and $B_i$ with a weight of $W_i$. Additionally, let the weight of a simple path connecting two vertices be the sum of the weights of the edges contained in the simple path.

Let us paint each vertex red or blue. Find the maximum value of the integer $X$ for which there is a coloring that satisfies the following condition:

• For every simple path connecting two different vertices painted in the same color, the weight of the simple path is at least $X$.

What is a simple path? For vertices $X$ and $Y$ in a graph $G$, a sequence of vertices $v_1,v_2, \ldots, v_k$ such that $v_1=X$, $v_k=Y$, and $v_i$ and $v_{i+1}$ are connected by an edge for each $1\leq i\leq k-1$ is called a walk from vertex $X$ to vertex $Y$. Furthermore, if $v_1,v_2, \ldots, v_k$ are all different, the walk is called a simple path (or just path).

Constraints

• $3 \leq N \leq 2 \times 10^5$
• $N-1 \leq M \leq \min(\frac{N(N-1)}{2},2 \times 10^5)$
• $1 \leq A_i < B_i \leq N$
• $1 \leq W_i \leq 10^9$
• The given graph is a simple connected undirected graph.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1 W_1
A_2 B_2 W_2
\vdots
A_M B_M W_M

Output

Print the answer.