// 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.1143607674727767x):
#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; 

}