#include<bits/stdc++.h>
#define N 3005
#define mk make_pair
using namespace std;
int a[N][N],T[N][N],F[N],vis[N];
int dead[N],pos[N],u,v,w,i,j,n,m,ans;
struct Heap{
  int id[N],len;
  void up(int x){
    for (;x>1;x>>=1)
      if (F[id[x]]>F[id[x>>1]])
        swap(pos[id[x]],pos[id[x>>1]]),swap(id[x],id[x>>1]);
      else return;
  }
  void pop(){
    pos[id[len]]=0;if ((--len)==0) return;
    id[1]=id[len+1];pos[id[1]]=1;
    for (int x=1;(x<<1)<=len;){
      int y=((x<<1)==n||F[id[x<<1]]>F[id[x<<1|1]])?(x<<1):(x<<1|1);
      if (F[id[x]]>=F[id[y]]) return;
      swap(pos[id[x]],pos[id[y]]);swap(id[x],id[y]);x=y;
    }
  }
  void add(int x){
    if (!pos[x]) id[pos[x]=++len]=x,up(len);
          else   up(pos[x]);
  }
  void clear(){len=0;}
}G;
void work(){
  for (int i=1;i<=n;i++)
    F[i]=-1e9,vis[i]=pos[i]=0;
  int S,p,q;
  for (int i=1;i<=n;i++) 
    if (!dead[i]) {S=i;break;}
  G.clear();F[S]=0;
  G.len=1;pos[G.id[1]=S]=G.id[1];
  while (G.len){
    int x=G.id[1];vis[x]=1;G.pop();
    for (int i=1;i<=*a[x];i++){
      int y=a[x][i];
      if (vis[y]) continue;
      F[y]+=T[x][y];G.add(y);
    }
    p=q;q=x;
  }int sum=0;
  for (int i=1;i<=*a[q];i++)
    sum+=T[q][a[q][i]];
  ans=min(ans,sum);
  for (int i=1;i<=n;i++)
    if (!dead[i]&&i!=q&&i!=p)
      if (T[q][i]&&!T[p][i]) a[p][++*a[p]]=i;
  for (int i=1;i<=n;i++)
    if (!dead[i]&&i!=p&&i!=q)
      T[i][p]+=T[i][q],T[p][i]+=T[q][i];
  dead[q]=1;
  for (int i=1;i<=n;i++)
    if (!dead[i]&&i!=q){
      int j=1;
      for (;j<=*a[i];j++)
        if (a[i][j]==q) break;
      if (j<=*a[i]){
        for (;j<*a[i];j++)
          a[i][j]=a[i][j+1];
        --(*a[i]);
      }
      if (!T[i][p]) continue;
      for (j=1;j<=*a[i];j++)
        if (a[i][j]==p) break;
      if (j>(*a[i])) a[i][++*a[i]]=p;
    }
}
int main(){
  while (scanf("%d%d",&n,&m)!=EOF){
    if (!n) return 0;
    memset(T,0,sizeof(T));
    for (i=1;i<=m;i++){
      scanf("%d%d%d",&u,&v,&w);
      if (u==v) continue;
      T[u][v]+=w;T[v][u]+=w;
    }
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        if (T[i][j]) a[i][++*a[i]]=j;
    ans=2e9;
    for (int tmp=n-1;tmp;tmp--)
      work();
    printf("%d\n",ans);
    for (i=1;i<=n;i++) *a[i]=dead[i]=0;
  }
}