#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) {return (n==0)?1:10*TEN(n-1);}
int bsr(int x) { return 31 - __builtin_clz(x); }

template <class E>
using Graph = vector<vector<E>>;

// NOT VERIFY
template<class D, D INF>
struct BidirectedCut {
    D sum = INF;
    template<class E>
    BidirectedCut(Graph<E> g) {
        int n = (int)g.size();
        int m_a = -1, m_b = -1;
        vector<D> dist_base(n, 0);
        for (int m = n; m > 1; m--) {
            int a, b;
            auto dist = dist_base;
            for (int i = 0; i < m; i++) {
                a = b; b = max_element(begin(dist), end(dist)) - begin(dist);
                if (i == m-1) sum = min(sum, dist[b]);
                dist[b] = -INF;
                for (E &e: g[b]) {
                    if (e.to == m_b) e.to = m_a;
                    if (dist[e.to] == -INF) continue;
                    dist[e.to] += e.dist;
                }
            }
            //merge a, b
            m_a = a; m_b = b;
            g[a].insert(end(g[a]), begin(g[b]), end(g[b]));
            g[b].clear();
            dist_base[b] = -INF;
        }
    }
};

/**
 * Dinic?????????????????§???
 *
 * ?????¨???????????¬????????????
 * template?????°???int V???????????°
 * Edge??????rev?????????
 * ---
 * void add_edge(Graph<Edge> &g, int from, int to, int cap) {
 *     g[from].push_back(Edge{to, cap, (int)g[to].size()});
 *     g[to].push_back(Edge{from, 0, (int)g[from].size()-1});
 * }
 * ---
 */
template<class C, C INF> // Cap
struct MaxFlow {
    int V;
    vector<int> level, iter;
    //g?????´?£????????????§??¨???
    template<class E>
    C exec(Graph<E> &g, int s, int t) {    
        V = (int)g.size();
        level.resize(V);
        iter.resize(V);
        C flow = 0;
        while (true) {
            bfs(g, s);
            if (level[t] < 0) return flow;
            fill_n(iter.begin(), V, 0);
            while (true) {
                C f = dfs(g, s, t, INF);
                if (!f) break;
                flow += f;
            }
        }
    }

    template<class E>
    void bfs(const Graph<E> &g, int s) {
        fill_n(level.begin(), V, -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int v = que.front(); que.pop();
            for (E e: g[v]) {
                if (e.cap <= 0) continue;
                if (level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    template<class E>
    C dfs(Graph<E> &g, int v, int t, C f) {
        if (v == t) return f;
        C res = 0;
        for (int &i = iter[v]; i < (int)g[v].size(); i++) {
            E &e = g[v][i];
            if (e.cap <= 0) continue;
            if (level[v] < level[e.to]) {
                C d = dfs(g, e.to, t, min(f, e.cap));
                if (d <= 0) continue;
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
        return res;
    }
};

int rand_int(int l, int r) { //[l, r)
    using D = uniform_int_distribution<int>;
    static random_device rd;
    static mt19937 gen(rd());
    return D(l, r-1)(gen);
}
bool solve() {
    int n, m;
    cin >> n >> m;
    if (!n) return false;
    struct Edge {
        int to;
        ll dist;
    };
    Graph<Edge> g(n);
    auto addEdge = [&](int a, int b, ll c) {
        g[a].push_back(Edge{b, c});
        g[b].push_back(Edge{a, c});
    };
    ll s = 0;
    for (int i = 0; i < m; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        if (c < 0) {
            s += c;
            continue;
        }
        addEdge(a, b, c);
    }
    cout << s+BidirectedCut<ll, TEN(15)>(g).sum << endl;
    return true;
}
 
int main() {
    while (solve()) {}
    return 0;
}

Measured memory_bytes: 3256