Problem Statement

There is a simple undirected graph with $N$ vertices and $M$ edges. The edges are initially painted white. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects vertex $A_i$ and vertex $B_i$, and the cost required to paint it black is $C_i$.

"Making a Q" means painting four or more edges so that:

• all but one of the edges painted black form a simple cycle, and
• the edge painted black not forming the cycle connects a vertex on the cycle and another not on the cycle.

Determine if one can make a Q. If one can, find the minimum total cost required to make a Q.

Constraints

• $4\leq N \leq 300$
• $4\leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i < B_i \leq N$
• $(A_i,B_i) \neq (A_j,B_j)$, if $i \neq j$.
• $1 \leq C_i \leq 10^5$
• All input values are integers.

Input

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

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

If one can make a Q, print the minimum total cost required to do so; otherwise, print $-1$.