#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int popcount(T n) { return n ? 1 + popcount(n & (n - 1)) : 0; }
#endif
#ifdef __GNUC__
template <class T> int popcount(T n);
template <> int popcount(unsigned int n) { return n ? __builtin_popcount(n) : 0; }
template <> int popcount(int n) { return n ? __builtin_popcount(n) : 0; }
template <> int popcount(unsigned long long n) { return n ? __builtin_popcountll(n) : 0; }
template <> int popcount(long long n) { return n ? __builtin_popcountll(n) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CL(arr, val) memset(arr, val, sizeof(arr))

#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
bool valid_pos(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

template <class T> void print(T a, int n, int br = 1, const string& deli = ", ") { cout << "{ "; for (int i = 0; i < n; ++i) { cout << a[i]; if (i + 1 != n) cout << deli; } cout << " }"; while (br--) cout << endl; }
template <class T> void print(const vector<T>& v, int br = 1, const string& deli = ", ") { print(v, v.size(), br, deli); }


template <class T>
class UnionFind
{
private:
	T* parent;
	T* rank;

public:
	int groups;
	
	UnionFind(int n)
		: groups(n)
	{
		parent = new T[n];
		rank = new T[n];
		for (int i = 0; i < n; ++i)
		{
			parent[i] = i;
			rank[i] = 0;
		}
	}

	void unite(T a, T b)
	{
		T root_a = find(a);
		T root_b = find(b);
		if (root_a == root_b)
			return;

		--groups;

		if (rank[root_a] < rank[root_b])
			parent[root_a] = root_b;
		else if (rank[root_a] > rank[root_b])
			parent[root_b] = root_a;
		else
		{
			parent[root_a] = root_b;
			++rank[root_a];
		}
	}

	bool same(T a, T b)
	{
		return find(a) == find(b);
	}

	T find(T e)
	{
		if (parent[e] == e)
			return e;
		else
			return parent[e] = find(parent[e]);
	}
};
class SCC
{
public:
	int V;
	vector<vector<int> > g;
	vector<vector<int> > rg;
	vector<int> vs;	// 帰りの順番, 後ろのほう要素は始点側
	vector<bool> used;
	vector<int> component;

	SCC(int V)
		: V(V), g(V), rg(V), vs(V), used(V), component(V) { }

	void add_edge(int from, int to)
	{
		g[from].push_back(to);
		rg[to].push_back(from);
	}

	void dfs(int v)
	{
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i)
			if (!used[g[v][i]])
				dfs(g[v][i]);
		vs.push_back(v);
	}

	void rdfs(int v, int k)
	{
		used[v] = true;
		component[v] = k;
		for (int i = 0; i < rg[v].size(); ++i)
			if (!used[rg[v][i]])
				rdfs(rg[v][i], k);
	}

	// 強連結成分の数を返す
	// O(V + E)
	// グラフの始点側の値(component[v])は小さい
	// 末端は大きい値, 最末端(component[v] == scc() - 1)
	int scc()
	{
		vs.clear();
		fill(used.begin(), used.end(), false);
		for (int i = 0; i < V; ++i)
			if (!used[i])
				dfs(i);

		fill(used.begin(), used.end(), false);
		int k = 0;
		for (int i = vs.size() - 1; i >= 0; --i)
			if (!used[vs[i]])
				rdfs(vs[i], k++);
		return k;
	}
};
int main()
{
	ios::sync_with_stdio(false);

	int n, m;
	while (cin >> n >> m, n)
	{
		vector<pint> e[128];	// (to, cost)
		UnionFind<int> uf(n);

		int res = 0;
		while (m--)
		{
			int x, y, c;
			cin >> x >> y >> c;
			if (c <= 0)
				res += c;
			else
			{
				e[x].push_back(pint(y, c));
				uf.unite(x, y);
			}
		}

		if (uf.groups == 1)
		{
			SCC scc(n);
			for (int i = 0; i < n; ++i)
				for (int j = 0; j < e[i].size(); ++j)
					scc.add_edge(i, e[i][j].first);
			scc.scc();

			int min_cost = INT_MAX;
			map<int, vector<int> > cost_in_scc;
			for (int i = 0; i < n; ++i)
			{
				for (int j = 0; j < e[i].size(); ++j)
				{
					int x = i, y = e[i][j].first, c = e[i][j].second;
					if (scc.component[x] != scc.component[y])
						min_swap(min_cost, c);
					else
						cost_in_scc[scc.component[x]].push_back(c);
				}
			}
			foreach (it, cost_in_scc)
			{
				vector<int>& v = it->second;
				sort(all(v));
				min_swap(min_cost, v[0] + v[1]);
			}

			res += min_cost;
		}

		cout << res << endl;
	}
}

Measured memory_bytes: 0