#include <stdio.h>
#include <string.h>
#define MaxN 110

const int oo = 0x7fffffff;
int g[MaxN][MaxN], d[MaxN];
bool used[MaxN], vst[MaxN];

int main()
{
    int min, n, m, max, tmp, pre, cur, a, b, w, cnt;

    while (scanf("%d%d", &n, &m), n) {
        min = oo, cnt = 0;
        memset(g, 0, sizeof(g));
        memset(used, 0, sizeof(used));
        int Res = 0;
        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &a, &b, &w);
            if (w < 0){
                Res += w;
                continue;
            }
            g[a][b] += w;
            g[b][a] = g[a][b];
        }
        if (n < 2) {
            printf("%d\n",Res);
            continue;
        }
        for (int i = 1; i < n; ++i) {
            memset(vst, 0, sizeof(vst));
            vst[0] = 1;
            cur = pre = d[0] = 0;
            for (int k = 1; k < n; ++k) d[k] = g[0][k];
            for (int j = i; j < n; ++j) {
                max = 0;
                pre = cur;
                for (int k = 0; k < n; ++k) {
                    if (vst[k] || used[k]) continue;
                    if (d[k] > max) {
                        max = d[k];
                        cur = k;
                    }
                }
                vst[cur] = 1;
                for (int k = 0; k < n; ++k) {
                    if (vst[k] || used[k]) continue;
                    d[k] += g[cur][k];
                }
            }
            used[cur] = 1;
            for (int j = 0; j < n; ++j) {
                if (j == pre || used[j]) continue;
                g[pre][j] += g[cur][j];
                g[j][pre] = g[pre][j];
            }
            tmp = 0;
            for (int j = 0; j < n; ++j) {
                if (used[j]) continue;
                tmp += g[cur][j];
            }
            if (tmp < min) min = tmp;
            else continue;
        }
        printf("%d\n", Res+min);
    }
    return 0;
}