#include <iostream>#include <cstdio>#include <cstring>using namespace std;struct Stoer_Wagner { static const int N=506, INF=(1<<30); int G[N][N], W[N], Merge[N], S, T, minCut, n; bool vs[N]; void init(int _n) { n=_n; memset(G, 0, sizeof G); } void BFS() { memset(vs, 0, sizeof vs); memset(W, 0, sizeof W); S=T=-1; int Max, id; for(int cnt=0; cnt<n; cnt++) { Max=-INF; for(int i=0; i<n; i++) if(!Merge[i] && !vs[i] && W[i]>Max) Max=W[i], id=i; if(id==T) return; S=T, T=id; minCut=Max; vs[id]=1; for(int i=0; i<n; i++) { if(Merge[i] || vs[i]) continue; W[i]+=G[id][i]; } } } int StoerWagner() { memset(Merge, 0, sizeof Merge); int ans=INF; for(int cnt=1; cnt<n; cnt++) { BFS(); if(minCut<ans) ans=minCut; if(ans==0) return ans; Merge[T]=1; for(int i=0; i<n; i++) { if(Merge[i]) continue; G[S][i]+=G[T][i]; G[i][S]+=G[i][T]; } } return ans; }};Stoer_Wagner ***;int n, m;int main() { while(scanf("%d%d", &n, &m)!=EOF) { ***.init(n); for(int i=0, a, b, c; i<m; i++) { scanf("%d%d%d", &a, &b, &c); ***.G[a][b]+=c; ***.G[b][a]+=c; } printf("%dn", ***.StoerWagner()); } return 0;}
