Problem Statement

You are given a simple connected undirected graph with $N$ vertices and $M$ edges, where the vertices are numbered from $1$ to $N$ and the edges are numbered from $1$ to $M$. Edge $i$ connects vertices $u_i$ and $v_i$ bidirectionally with weight $w_i$.

Consider tours that start from some vertex, pass through every vertex exactly $1$ time, and return to the starting point. Find the weight of such a tour whose weight is minimum.

It can be shown that at least $1$ such tour exists under the constraints of this problem.

Input

$N\ M$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_M\ v_M\ w_M$

• All inputs are integers.
• The given graph is simple and connected.
• $2 \leq N \leq 500$
• $M=\displaystyle \frac{N(N-1)}{2}$
• $1 \leq u_i,v_i \leq N$
• $w_i=1$

Output

Output on $1$ line the minimum weight of a tour satisfying the conditions in the problem statement.

Print a newline at the end.

Sample

2 1
1 2 1

2