// Original C++ solution (slower):
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <set>

#include <stack>

#include <queue>

#include <vector>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

typedef long long LL;

#define NN 120

#define INF 1LL << 60



LL vis[NN];

LL wet[NN];

LL combine[NN];

LL map[NN][NN];

LL S, T, minCut, N;

void Search(){

     LL i, j, Max, tmp;

     memset(vis, 0, sizeof(vis));

     memset(wet, 0, sizeof(wet));

     S = T = -1;

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

         Max = -INF;

         for (j = 0; j < N; j++){

             if (!combine[j] && !vis[j] && wet[j] > Max){

                tmp = j;

                Max = wet[j];

             }

         }

         if (T == tmp) return;

         S = T; T = tmp;

         minCut = Max;

         vis[tmp] = 1;

         for (j = 0; j < N; j++){

             if (!combine[j] && !vis[j]){

                wet[j] += map[tmp][j];

             }

         }

     }

}

LL Stoer_Wagner(){

    LL i, j;

    memset(combine, 0, sizeof(combine));

    LL ans = INF;

    for (i = 0; i < N - 1; i++){

        Search();

        if (minCut < ans) ans = minCut;

        if (ans == 0) return 0;

        combine[T] = 1;

        for (j = 0; j < N; j++){

            if (!combine[j]){

               map[S][j] += map[T][j];

               map[j][S] += map[j][T];

            }

        }

    }

    return ans;

}

int main(){

	LL u, v, m, c;

	while( scanf("%lld%lld", &N, &m) && (N+m) ){

		memset( map, 0, sizeof( map ) );

		LL ans = 0;

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

			scanf("%lld%lld%lld", &u, &v, &c);

			if( c < 0 ) ans += c;

			else if( u != v ){

				map[u][v] += c;

				map[v][u] += c;

			}

		}

		ans += Stoer_Wagner();

		printf("%lld\n", ans);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#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 ;

}

// Fastest known solution for this problem: