每一个生活在 $Bzeroth$ 大陆的精灵都知道，若想毁灭他们深爱的这片土地，必须要先摧毁守护 $Bzeroth$ 大陆的 $N$ 个能量核心。

这 $N$ 个能量核心由诸神修建的 $M$ 条秩序神链沟通，其中第 $i$ 条秩序神链沟通了第 $u_i$ 和第 $v_i$ 个核心，稳定程度为 $w_i$。

最开始，这 $N$ 个能量核心是连通的（即任意两个能量核心均能通过神链直接或间接沟通）。地灾军团的军师黑袍得知，他们可以摧毁若干神链使得这 $N$ 个能量核心恰好被分成两个连通块，从而削弱 $Bzeroth$ 大陆的防卫能量。

由于被摧毁后的防卫能量等于未被摧毁的神链的稳定程度之和，所以他找到了精灵王国最好的工程师，同时也是地灾军团潜伏在 $Bzeroth$ 大陆多年的间谍——你，来设计出最优的方案，使得未被摧毁的神链的稳定程度之和最小。

输入格式

第一行为 $2$ 个整数 $N、M$ 。

接下来 $M$ 行每行三个正整数 $u_i、v_i、w_i$。

输出格式

输出最优情况下征集到的物资总和。

样例

input

5 5
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5

output

6

限制与约定

对于 $50\texttt{%}$ 的数据：$1 \leq N、M \leq 15$。

对于 $70\texttt{%}$ 的数据：$1 \leq N \leq 15$。

另有 $20\texttt{%}$ 的数据：$M \leq N$。

对于 $100\texttt{%}$ 的数据：$1 \leq N、M \leq 152501$，$1 \leq u_i、v_i \leq N$，$1 \leq w_i \leq 10^9$。

时间限制：$1\texttt{s}$

空间限制：$128\texttt{MB}$