#include<stdio.h>
#include<string.h>
long m,n,a,b,c;
long val[105];
long v[105][105];
int getans(){
	int ans,i,j,k,r,s1,s2;
	long a[105];
	long mark[105];
	long w[105];
	memset(w,0,sizeof(w));
	if (n==2){
		return val[0];
	}
	a[0]=0;
	for (i=0;i<n;i++)
	  mark[i]=1;
	ans=val[a[0]];
	for (i=1;i<=n-1;i++){
    r=0;
    mark[a[0]]=2;
	  for (j=0;j<n;j++){
			if (mark[j]==1)
			  w[j]=v[a[0]][j];
		}
		while (true){
			k=-1;
			for (j=0;j<n;j++){
				if (mark[j]==1 &&(k==-1 || w[j]>w[k]))
			  	k=j;
			}
			if (k==-1)
			  break;
	    r++;
	    a[r]=k;
	    ans=ans<val[k]?ans:val[k];
	    mark[k]=2;
	    for (j=0;j<n;j++){
    		if (mark[j]==1)
    		  w[j]+=v[j][k];
    	}
		}
		s1=a[r-1];s2=a[r];
		val[s1]+=val[s2];
		val[s1]-=v[s1][s2]*2;
		mark[s2]=3;
		for (j=0;j<n;j++){
			if (mark[j]!=3){
				v[s1][j]=v[j][s1]=v[s1][j]+v[j][s2];
        mark[j]=1;
			}
	  }
		v[s1][s2]=v[s2][s1]=0;
	}
	return ans;
}
int main(){
  while (scanf("%d %d",&n,&m)==2){
  	int nowans=0;
		if (n==0)
  	  return 0;
  	memset(val,0,sizeof(val));
  	memset(v,0,sizeof(v));
		  for (int j=0;j<m;j++){
  			scanf("%d %d %d",&a,&b,&c);
  			if (c<=0)
  			  nowans+=c;
			  else{
	  			v[a][b]=v[b][a]=v[a][b]+c;
  				val[a]+=c;
  				val[b]+=c;
			  }
			}
		printf("%d\n",nowans+getans());
	}
}