#include <fstream>
#include <cstdio>
using namespace std;
const int inf=1000000000;
int mat[64][64],in[64],out[64],n,m,cap[64][64],cost[64][64],prev[64],sol;
int bf(){
 int q[64*64],st,dr,d[64],used[64],i,nod;
 for(i=1;i<=n+1;i++){d[i]=inf;used[i]=0;}
 d[0]=0;q[st=dr=1]=0;
 while(st<=dr){
  nod=q[st];used[nod]=0;
  for(i=1;i<=n+1;i++){
   if(cap[nod][i]>0&&d[i]>d[nod]+cost[nod][i]){
     d[i]=d[nod]+cost[nod][i];prev[i]=nod;
     if(!used[i]){q[++dr]=i;used[i]=1;}
    }
   }
  st++;
 }
 if(d[n+1]==inf){return 0;}
 return d[n+1];
}
int i,j,k,a,b,c,temp,min_cap,nod;
int main(){
 ifstream cin("traseu.in");
 ofstream cout("traseu.out");
 cin>>n>>m;
 for(i=1;i<=m;i++){
  cin>>a>>b>>c;
  ++out[a];++in[b];
  cost[a][b]=c;cost[b][a]=-c;cap[a][b]=inf;
  sol+=c;
 }
 for(i=1;i<=n;i++){
  if(in[i]>out[i]){cap[0][i]=in[i]-out[i];}
  else if(in[i]<out[i]){cap[i][n+1]=out[i]-in[i];}
 }
 while(temp=bf()){
  min_cap=inf;
  for(nod=n+1;nod;nod=prev[nod]){if(cap[prev[nod]][nod]<min_cap){min_cap=cap[prev[nod]][nod];}}
  for(nod=n+1;nod;nod=prev[nod]){
    cap[prev[nod]][nod]-=min_cap;
    cap[nod][prev[nod]]+=min_cap;
   }sol+=temp*min_cap;
  }
  cout<<sol;
  return 0;
}