3155: 彩虹岛之刃

彩虹岛很久之前是一片沼泽，随着全球变暖，逐渐开始显露出一些小岛，彩虹岛也逐渐出现了彩虹岛帝国。可是残暴的彩虹岛-炀帝，他在位期间修建了很多的桥，连接了各个岛屿，方便自己玩乐。


虽然一定程度上有利于了居民之间的通行，但是耗费了大量的人力物力。
慢慢的，手持彩虹岛之刃的英雄人物——魔笛·里奥出现了，带领大家击溃了炀帝的军队，
重新建立了令大家开心快乐的彩虹岛之国。但是英勇而又明智的里奥马上又意识到需要把这些小岛居民分开两部分治理，但是由于拆掉小岛之间的桥是需要花费彩虹岛之刃的剑气的，所以他想选择一些边，删除之后，可以使得将全部小岛分为两个不相交的小岛集合，
并且删掉的这些边消耗的彩虹岛之刃剑气的和最小。

输入的第一行包含两个整数 $n$ 和 $m$ ，表示节点数和边数。$2\le n \le 1000$，$1\le m \le 1000000$

接下来的 m 行，每行包含三个整数 u,v,c，表示连接小岛编号为 u 和 v 的桥，拆掉它需要消耗的彩虹岛之刃的剑气。

$1\le u,v\le n,~~~0≤c≤10^4$。题目保证无重边、无自环、联通。

输出消耗的最少的彩虹之刃剑气之和

5 7
1 2 4
1 3 5
2 3 2
2 4 1
3 4 6
3 5 3
4 5 4

7