// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.1117158153738695x):
// I'm the Topcoder

//C

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include <math.h>

#include <time.h>

//C++

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <cctype>

#include <stack>

#include <string>

#include <list>

#include <queue>

#include <map>

#include <vector>

#include <deque>

#include <set>

using namespace std;



//*************************OUTPUT*************************

#ifdef WIN32

#define INT64 "%I64d"

#define UINT64 "%I64u"

#else

#define INT64 "%lld"

#define UINT64 "%llu"

#endif



//**************************CONSTANT***********************

#define INF 0x7F7F7F7F

#define eps 1e-8

#define PI acos(-1.)

#define PI2 asin (1.);

typedef long long LL;

//typedef __int64 LL;   //codeforces

typedef unsigned int ui;

typedef unsigned long long ui64;

#define MP make_pair

typedef vector<int> VI;

typedef pair<int, int> PII;

#define pb push_back

#define mp make_pair



//***************************SENTENCE************************

#define CL(a,b) memset (a, b, sizeof (a))

#define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b))



//****************************FUNCTION************************

template <typename T> double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); }

template <class T> inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; }

template <typename T> inline T square(T va, T vb) { return va * va + vb * vb; }



// aply for the memory of the stack

#pragma comment (linker, "/STACK:1024000000,1024000000")

//end



#define CY 105

typedef int typec;



bool inset[CY], vis[CY];

typec wage[CY];

int g[CY][CY];

int N, M;



typec Search(int n, int &s, int &t) {

	memset(vis, false, n * sizeof(vis[0]));

	memset(wage, 0, n * sizeof(wage[0]));

	s = t = -1;

	typec cf, mx;

	int u = 0;

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

		mx = -INF;

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

			if (!inset[j] && !vis[j] && mx < wage[j]) {

				mx = wage[u = j];

			}

		}

		if (u == t) return cf;

		s = t; t = u;

		cf = mx;

		vis[u] = true;

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

			if (!inset[v] && !vis[v]) {

				wage[v] += g[u][v];

			}

		}

	}

	return cf;

}



typec Stoer_Wagner(int n) {

	int s, t;

	typec ans = INF, cf;

	memset(inset, false, n * sizeof(inset[0]));

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

		cf = Search(n, s, t);

		ans = min(ans, cf);

		if (ans == 0) return ans;

		inset[t] = true;

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

			if (!inset[j] && j != s) {

				g[s][j] += g[t][j];

				g[j][s] += g[j][t];

			}

		}

	}

	return ans;

}



int main(void) {

	while (2 == scanf("%d%d", &N, &M)) {

		if (N == 0 && M == 0) break;

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

		int ans = 0, u, v, c;

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

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

			if (c > 0) g[u][v] += c, g[v][u] += c;

			else ans += c;

		}

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

	}

	return 0;

}