//Start: 2024-11-15 19:50:48
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt, __func__, __LINE__, ##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=1e5+5;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n,m;
namespace Flow_Cost{
  const int N=2005,M=20005,inf=1e9;
  int n,s,t;
  int h[N],ce=1;struct Edge{int v,w,c,nxt;}e[M<<1];
  void addedge(int u,int v,int w,int c){
    e[++ce]={v,w,c,h[u]};h[u]=ce;
    e[++ce]={u,0,-c,h[v]};h[v]=ce;
  }
  int dis[N],pre[N];bool vis[N];deque<int>q;
  bool spfa(){
    for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
    dis[s]=0;q.push_back(s);
    while(!q.empty()){
      int u=q.front();q.pop_front();
      if(u==t) continue;
      for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(e[i].w==0||e[i].c+dis[u]>=dis[v]) continue;
        dis[v]=e[i].c+dis[u],pre[v]=i;
        if(!vis[v]){
          vis[v]=1;
          if(q.empty()||dis[v]<dis[q.front()]) q.push_front(v);
          else q.push_back(v);
        }
      }
      vis[u]=0;
    }return dis[t]<inf;
  }
  ll Cost(int S,int T){
    n=t=T;s=S;
    int flow=0,cost=0;
    For(i,1,2){
      spfa();cost+=dis[t];
      for(int i=t;i!=s;i=e[pre[i]^1].v) e[pre[i]].w--,e[pre[i]^1].w++;
    }return cost;
  }void clear(int n){For(i,1,n) h[i]=0;ce=1;}
}
using Flow_Cost::addedge,Flow_Cost::Cost;
signed LJY(){
  while(scanf("%d%d",&n,&m)==2){
    Flow_Cost::clear(2*n+2);
    int S=n*2+1,T=S+1;
    For(i,1,n) addedge(i,i+n,1,0);
    addedge(S,1+n,2,0);addedge(n,T,2,0);
    For(i,1,m){
      int u=read(),v=read();
      addedge(u+n,v,1,read());
    }printf("%lld\n",Cost(S,T));
  }
  return 0;
}