Problem: Mr. Dango's family has an extremely huge number of members. Once it had about 100 members, and now it has as many as population of a city. It is jokingly guessed that the member might fill this planet in the near future.

Mr. Dango's family, the huge family, is getting their new house. Scale of the house is as large as that of town.

They all had warm and gracious personality and were close each other. However, in this year the two members of them became to hate each other. Since the two members had enormous influence in the family, they were split into two groups.

They hope that the two groups don't meet each other in the new house. Though they are in the same building, they can avoid to meet each other by adjusting passageways.

Now, you have a figure of room layout. Your task is written below.

You have to decide the two groups each room should belong to. Besides you must make it impossible that they move from any rooms belonging to one group to any rooms belonging to the other group. All of the rooms need to belong to exactly one group. And any group has at least one room.

To do the task, you can cancel building passageway. Because the house is under construction, to cancel causes some cost. You'll be given the number of rooms and information of passageway. You have to do the task by the lowest cost.

Please answer the lowest cost.

By characteristics of Mr. Dango's family, they move very slowly. So all passageways are escalators. Because of it, the passageways are one-way.

Constraints

* 2 ≤ n  ≤ 100
* -10,000 ≤ Ci ≤ 10,000
* Y1 ... Ym can't be duplicated integer by each other.

Input

The input consists of multiple datasets. Each dataset is given in the following format.


n m
X1 Y1 C1
...
Xm Ym Cm


All numbers in each datasets are integers. The integers in each line are separated by a space.

The first line of each datasets contains two integers. n is the number of rooms in the house, m is the number of passageways in the house. Each room is indexed from 0 to n-1.

Each of following  m  lines gives the details of the passageways in the house. Each line contains three integers. The first integer Xi is an index of the room, the starting point of the passageway. The second integer Yi is an index of the room, the end point of the passageway. The third integer Ci is the cost to cancel construction of the passageway. The passageways, they are escalators, are one-way. The last dataset is followed by a line containing two zeros (separated by a space).

Output

For each dataset, print the lowest cost in a line. You may assume that the all of integers of both the answers and the input can be represented by 32 bits signed integers.

Example

Input

3 2
0 1 2
1 2 1
2 1
0 1 100
2 1
0 1 0
2 1
0 1 -1
0 0


Output

1
100
0
-1

Solution (in CPP):

Solution:
#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;
	}
}