Description

Given a connected graph G = (V, E) and a weight function w: E → N. Let H be a subgraph of G, we define the weight of H w(H) to be the sum of weight of all the edge in H. 

In this problem, you need to answer the weight of the second minimum spanning tree. Namely, let T₁ be a minimum spanning tree of G, find the weight of another spanning tree T₂ such that w(T₁) <= w(T₂) and w(T₂) <= w(T'), where T' is a spanning tree of G, T' ≠ T₁.

Input

There are two integer in the first line, n, m, which represent |V|, |E|.

In the following m lines, each line contains three integer: u, v, c, which is the endpoints of the edge and the weight of the edge respectivlely.

Constraint

• 3 <= n <= 1000
• n <= m <= min{2000, n x (n-1) / 2}
• In each line, 1 <= u, v <= n, u ≠ v
• 1 <= c <= 10⁹
• It is guaranteed that the answer exists.

Output

Output the answer in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss