#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;

}