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

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <map>

#include <string>

#include <queue>

using namespace std;

#define SZ(v) ((int)(v).size())

const int maxint = -1u>>1;

const int maxn = 100 + 30;

typedef long long ll;



int n, m;

ll adj[maxn][maxn];

int f[maxn], bestf[maxn];

int find(int v) {

    if (v != bestf[v]) {

        return bestf[v] = find(bestf[v]);

    }

    return v;

}

int bestff;

int v[maxn];

ll w[maxn];

bool a[maxn];

vector<pair<int, int> > res;

ll mincut() {

    ll ans = (-1ull) >> 1;

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

        //for (int j = 0; j < n; ++j) {

            //adj[i][j] = -adj[i][j];

        //}

    //}

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

        f[i] = v[i] = i;

    }

    for (int t = n; t > 1; --t) {

        a[0] = true;

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

            a[i] =false;

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

        }

        int prev = v[0];

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

            int zj = -1;

            for (int j = 1; j < t; ++j) {

                if (a[j] == false && (zj == -1 || w[j] > w[zj])) {

                    zj = j;

                }

            }

            a[zj] = true;

            if (i == t - 1) {

                if (w[zj] < ans) {

                    ans = w[zj];

                    copy(f, f + n, bestf);

                    bestff = v[zj];

                }

                for (int k = 0; k < t; ++k) {

                    adj[v[k]][prev] = adj[prev][v[k]] += adj[v[zj]][v[k]];

                }

                f[v[zj]] = prev;

                v[zj] = v[t - 1];

                break;

            }

            prev = v[zj];

            for (int j = 1; j < t; ++j) {

                if (a[j] == false) {

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

                }

            }

        }

    }

    //bool flag[maxn] = {};

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

        //if (find(i) == bestff) {

            //flag[i] = true;

        //}

    //}

    //res.clear();

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

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

            //if (flag[i] == flag[j] && save[i][j]) {

                //res.push_back(make_pair(i, j));

            //}

        //}

    //}

    return ans;

}



void gao() {

    ll ans = 0;

    memset(adj, 0, sizeof(adj));

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

        ll c;

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

        if (c < 0) {

            ans += c;

        } else {

            adj[a][b] = adj[b][a] = adj[a][b] + c;

        }

    }

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

}



int main() {

    while (scanf("%d%d", &n, &m) == 2 && (n || m)) {

        gao();

    }

    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: