#include<bits/stdc++.h>
using namespace std;
using Int = long long;
struct SCC{
  int n;
  vector<vector<int> > G,rG,T,C;
  vector<int> vs,used,belong;
  SCC(){};
  SCC(int sz):n(sz),G(sz),rG(sz),used(sz),belong(sz){}
 
  void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
  }
 
  void dfs(int v){
    used[v] = 1;
    for(int i=0;i<(int)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] = 1;
    belong[v] = k;
    C[k].push_back(v);
    for(int i=0;i<(int)rG[v].size();i++) {
      if(!used[rG[v][i]]) rdfs(rG[v][i],k);
    }
  }
 
  int build(){
    fill(used.begin(),used.end(),0);
    vs.clear();
    for(int v=0;v<n;v++){
      if(!used[v]) dfs(v);
    }
 
    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
      if(!used[vs[i]]){
    T.push_back(vector<int>());
    C.push_back(vector<int>());
    rdfs(vs[i],k++);
      }
    }
    return k;
  }
 
};
 
struct UnionFind{
  int n;
  vector<int> r,p;
  UnionFind(int n):n(n),r(n,1),p(n){iota(p.begin(),p.end(),0);}
  int find(int x){
    if(x==p[x]) return x;
    return p[x]=find(p[x]);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};
 
signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n,m;
  while(cin>>n>>m,n){
    vector<int> x(m),y(m),c(m);
    int ans=0;
    UnionFind uf(n);
    SCC scc(n);
    for(int i=0;i<m;i++){
      cin>>x[i]>>y[i]>>c[i];
      if(c[i]<=0) ans+=c[i];
      else{
	scc.add_edge(x[i],y[i]);
	uf.unite(x[i],y[i]);
      }
    }
    if(uf.r[uf.find(0)]!=n){
      cout<<ans<<endl;
      continue;
    }
    scc.build();
    //cout<<ans<<endl;
    auto b=scc.belong;
    vector<int> v;
    int t=-1;
    for(int i=0;i<m;i++){
      if(c[i]<=0) continue;
      if(b[x[i]]==b[y[i]]){
	v.emplace_back(c[i]);
	continue;
      }
      if(t<0||c[i]<t) t=c[i];
    }
    sort(v.begin(),v.end());
    if(!v.empty()&&(t<0||v[0]+v[1]<t)) t=v[0]+v[1];
    cout<<ans+t<<endl;
  }
  return 0;
}