#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int INF=0x3f3f3f3f;const int MAX_N=510;int v[MAX_N],w[MAX_N],c[MAX_N],g[MAX_N][MAX_N],S,T,now,N,M,x,y,z;void search(){    int i,j,k,t;    for(i=0;i<N;i++)v[i]=w[i]=0;    for(S=T=-1,i=0;i<N;i++){        for(k=-INF,j=0;j<N;j++)if(!c[j]&&!v[j]&&w[j]>k)k=w[t=j];        if(T==t)return;        S=T,T=t,now=k,v[t]=1;        for(j=0;j<N;j++)if(!c[j]&&!v[j])w[j]+=g[t][j];    }}int stoerwagner(){    int i,j,ans=INF;    for(i=0;i<N;i++)c[i]=0;    for(i=0;i<N-1;i++){        search();        if(now<ans)ans=now;        if(ans==0)return 0;        for(c[T]=1,j=0;j<N;j++)if(!c[j])g[S][j]+=g[T][j],g[j][S]+=g[j][T];    }return ans;}void init(){    memset(g,0,sizeof(g));    while(M--)scanf("%d%d%d",&x,&y,&z),g[x][y]+=z,g[y][x]+=z;}void solve(){    printf("%d\n",stoerwagner());}int main(){    while(~scanf("%d%d",&N,&M)){        init();        solve();    }return 0;}

#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int INF=0x3f3f3f3f;const int MAX_N=510;int G[MAX_N][MAX_N],v[MAX_N],f[MAX_N],N,M,vis[MAX_N];int Stoer_Wagner(){    int ret=INF;    for(int i=1;i<=N;i++)v[i]=i;    while(N>1){        int k,lst=v[1];        memset(vis,0,sizeof(vis));        memset(f,0,sizeof(f));        vis[v[1]]=1;        for(int i=2;i<=N;i++){            k=1;            for(int j=2;j<=N;j++)if(!vis[v[j]]&&(f[v[j]]+=G[lst][v[j]])>f[v[k]])k=j;            vis[v[k]]=1;            if(i<N)lst=v[k];        }ret=min(ret,f[v[k]]);        for(int j=1;j<=N;j++)G[v[j]][lst]=G[lst][v[j]]=G[lst][v[j]]+G[v[k]][v[j]];        v[k]=v[N--];    }return ret;}void init(){    memset(G,0,sizeof(G));	for(int i=1;i<=M;i++){        int x,y,z;        scanf("%d%d%d",&x,&y,&z);        ++x;++y;        G[x][y]+=z;G[y][x]+=z;    }}void solve(){printf("%d\n",Stoer_Wagner());}int main(){    while(~scanf("%d%d",&N,&M)){        init();        solve();    }return 0;}