每一个生活在 $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}$