// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#include <cmath>

#include <string>

#include <cctype>

#include <map>

#include <iomanip>

                   

using namespace std;

                   

#define eps 1e-8

#define pi acos(-1.0)

#define inf 1<<30

#define linf 1LL<<60

#define pb push_back

#define lc(x) (x << 1)

#define rc(x) (x << 1 | 1)

#define lowbit(x) (x & (-x))

#define ll long long

#define maxn 110



int maz[maxn][maxn];

int n,m;



int stoer_wagner(int n){

    bool vis[maxn];

    int node[maxn],dis[maxn];

    int maxj,prev;

    int ans=inf;

    memset(dis,0,sizeof(dis));

    for (int i=0; i<n; i++)node[i]=i;

    while (n>1) {

        prev=0;

        maxj=1;

        memset(vis,false,sizeof(vis));

        vis[node[0]]=true;

        for (int i=1; i<n; i++) { 

            dis[node[i]]=maz[node[0]][node[i]];

            if (dis[node[i]]>dis[node[maxj]])

                maxj=i; 

        } 

        for (int i=1; i<n; i++) {

            if (i==n-1) { //蜿ェ蜑ゥ譛?錘荳?クェ轤ケ蟆ア蠑?ァ句粋蟷カ轤ケ

                ans=(dis[node[maxj]]<ans?dis[node[maxj]]:ans);

                for (int k=0; k<n; k++) {//蜷亥ケカ轤ケ?梧峩譁ー霎ケ譚??邉サ

                    maz[node[k]][node[prev]]+=maz[node[k]][node[maxj]];

                    maz[node[prev]][node[k]]=maz[node[k]][node[prev]];

                } 

                node[maxj]=node[--n];//郛ゥ轤ケ

            } 

            prev=maxj;

            vis[node[maxj]]=true;

            maxj=-1;

            for (int k=1; k<n; k++) {

                if(!vis[node[k]]) {

                    dis[node[k]]+=maz[node[prev]][node[k]];

                    if(maxj==-1 || dis[node[k]]>dis[node[maxj]])

                        maxj=k; 

                } 

            }

        }

    }

    return ans;

}



int main(){

    while(~scanf("%d%d",&n,&m)){

		if(n==0&&m==0)	break;

        memset(maz,0,sizeof(maz));

        int a,b,c,res=0;            

        for (int i=0; i<m; i++) {

            scanf("%d%d%d",&a,&b,&c);

			if(c<0){

				res+=c;

			continue;

			}

            maz[a][b]+=c;

            maz[b][a]+=c;

        } 

        printf("%d\n",stoer_wagner(n)+res);

    }

    return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 4.163460338239305x):
#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;





const int inf = 0x3f3f3f3f ;

const int maxw = 1000 ;

int g[105][105] , w[105] ;

int a[105] , v[105] , na[105] ;

int n , m ;

int mincut( int n ) {

	int i , j, pv , zj ;

	int best = inf ;

	for( i = 0 ; i < n; i ++ ) {

		v[i] = i ;

	}

	while( n > 1 ) {

		for( a[v[0]] = 1 , i = 1 ; i < n; i ++ ) {

			a[v[i]] = 0 ; na[i-1] = i ;

			w[i] = g[v[0]][v[i]] ;

		}

		for( pv = v[0] ,i = 1 ; i < n ; i ++ ) {

			for( zj = -1 , j = 1 ; j < n ; j ++ ) 

				if( !a[v[j]] && (zj<0||w[j]>w[zj]))

					zj = j ;

				a[v[zj]] = 1 ;

				if( i == n - 1 ) {

					if( best > w[zj] ) best = w[zj] ;

					for( i = 0 ; i < n;  i++ ) {

						g[v[i]][pv] = g[pv][v[i]] +=g[v[zj]][v[i]] ;

					}

					v[zj] = v[--n] ;

					break;

				}

				pv = v[zj] ;

				for( j = 1 ; j < n; j ++ ) if( !a[v[j]])

					w[j] += g[v[zj]][v[j]] ;

		}

	}

	return best ;

}



int main(){

	while( scanf( "%d%d" , &n , &m ) != EOF ) {

		if( n == 0 && m == 0 ) break;

		memset( g , 0 , sizeof(g) ) ;

		int ans = 0 ;

		int i ;

		for( i = 1 ; i <= m ;i ++ ) {

			int from , to ,val ;

			scanf( "%d%d%d" , &from , &to , &val ) ;

			if( val < 0 ) {

				ans += val ;

				continue ;

			}

			if( g[from][to] == inf ) {

				g[from][to] = val ;

			}else{

				g[from][to] += val ;

			}

			g[to][from] = g[from][to] ;

		}

		printf( "%d\n" , ans + mincut(n) )  ;

	}

	return 0 ;

}