#3345. Pku2914 Minimum Cut

内存限制:512 MiB 时间限制:3 Sec

题目描述

有一个N(<=500)的无向图,求将这个图断成两个联通块需要删除的边的边权和最小值。

输入格式

两个数n,m,然后m个数每行三个数a,b,c,表示a和b这两个点的连系为c (不会重复出现一对a和b,无序)

输出格式

 
一个数表示最小的联系度和(即无向图最小割)

样例

样例输入


			
3 3
1 2 1
2 3 1
3 1 2

样例输出


			
2

数据范围与提示



m<=10000