Robust Power Grid Sabotage

During the winter of \(1948\), an underground squad in Nanjing planned to attack the Tiger Bridge Prison in order to rescue hundreds of prisoners. The prison is secured by \(N\) layers of electric grids (numbered \(1,2,\dots, N\)), where the first layer is connected to high voltage. There are \(M\) high voltage lines; the \(i\)-th line connects grid \(a_i\) and \(b_i\) and requires \(T_i\) agents to sabotage. However, a spy has secretly added one extra high voltage line (whose agent requirement is unknown) between two grids to foil the plan.

In order for the rescue to succeed, the squad must sabotage exactly one of the existing high voltage lines such that, no matter which two grids the extra line connects, there is at least one grid that will not receive power. In other words, after removing one chosen line and then adding an extra line (which is guaranteed not to duplicate an already existing connection), the resulting network must remain disconnected: the high-voltage source (grid 1) cannot reach every grid.

Formally, let the original graph \(G=(V,E)\) have \(|V|=N\) and \(|E|=M\) with each edge \(e_i=(a_i,b_i)\) having a cost \(T_i\). A secret edge \(f\) (which is not in \(E\)) is added arbitrarily. The squad needs to choose one edge \(e\) to remove such that for every possible secret edge \(f\), the graph \((V, E\setminus\{e\} \cup \{f\})\) is disconnected (i.e. there is at least one grid not connected to grid 1).

A necessary and sufficient condition for an edge \(e\) to yield such a robust disconnection is that when \(e\) is removed, the graph splits into two connected components \(A\) and \(B\) with grid 1 entirely in one component, and all possible cross edges between \(A\) and \(B\) already existed in \(G\). (Note that the secret edge can only be added if it does not already exist in \(G\).)

Your task is to determine the minimum number of agents required (i.e. the minimum \(T_i\)) for such a sabotage. If no single edge can guarantee a disconnection under the above condition, output -1.

Decision time... the fate of the rescue mission lies in your hands!

inputFormat

The first line contains two integers \(N\) and \(M\) \((2 \le N, M \le 10^5)\), representing the number of electric grids and the number of high voltage lines.

Then \(M\) lines follow. The \(i\)-th line contains three integers \(a_i, b_i\) and \(T_i\) \((1 \le a_i, b_i \le N, a_i \ne b_i, 1 \le T_i \le 10^9)\) meaning that there is a high voltage line connecting grid \(a_i\) and grid \(b_i\) which requires \(T_i\) agents to sabotage.

It is guaranteed that the original graph \(G\) is connected and that no pair \((a_i, b_i)\) appears more than once.

outputFormat

Output a single integer: the minimum number of agents required for a sabotage that guarantees that after the extra secret high voltage line (which does not duplicate an existing connection) is added, there is at least one grid not receiving power. If no such sabotage is possible, output -1.

sample

4 3
1 2 5
1 3 3
1 4 10

-1