#include <fstream>
using namespace std;
#define nmax 65
#define inf 0x3f3f3f
#define ll long long
#define min(a,b) ((a<b)?(a):(b))
ifstream f("traseu.in");
ofstream g("traseu.out");
int n,m;
int C[nmax][nmax],pre[nmax];
int gin[nmax],gout[nmax];
int cap[nmax][nmax],fx[nmax][nmax];
ll drum[nmax],sol,dmin;
bool viz[nmax];
int Q[1000];
#define Q (Q-1)
bool eok;
struct graf
 {
 int x;
 graf *urm;
 };
graf *G[nmax],*G1;
void add(graf *&g,int x)
 {
 graf *p=new graf;
 p->x=x;
 p->urm=g;
 g=p;
 }
void read()
 {
 f>>n>>m;
 int x,y,c,i;
 for(i=1;i<=m;i++)
  {
  f>>x>>y>>c;
  C[x][y]=c;
  C[y][x]=-c;
  add(G[x],y);
  add(G[y],x);
  if(y==1)
   add(G1,x);
  ++gout[x];
  ++gin[y];
  }
 for(i=1;i<=n;i++)
  for(graf *g=G[i];g!=NULL;g=g->urm)
   {
   if(C[i][g->x]>0)
	cap[i][g->x]=gin[i];
   }
 }
void BF()
 {
 int k=0,i,j,x,fxmin;
 dmin=inf;
 for(i=2;i<=n;i++) drum[i]=inf;
 j=0;
 Q[++k]=1;
 viz[1]=true;
 for(i=1;i<=k;++i)
  {
  x=Q[i];
  for(graf *g=G[x];g!=NULL;g=g->urm)
   {
   if(drum[g->x]>drum[x]+C[x][g->x] && cap[x][g->x]-fx[x][g->x]>0)
    {
    drum[g->x]=drum[x]+C[x][g->x];
	pre[g->x]=x;
	if(!viz[g->x])
	 {
	 Q[++k]=g->x;
	 viz[g->x]=true;
	 }
    }
   }
  viz[x]=false;
  }
 for(graf *g=G1;g!=NULL;g=g->urm)
  {
  if(drum[g->x]+C[g->x][1]<dmin && cap[g->x][1]-fx[g->x][1]>0)
   {
   dmin=drum[g->x]+C[g->x][1];
   pre[1]=g->x;
   }
  }
 
 if(dmin==inf)
  return;
 eok=true;
 fxmin=inf;
 sol+=dmin;
 i=1;
 do
  {
  fxmin=min(fxmin,cap[pre[i]][i]);
  i=pre[i];
  }while(i!=1);
 i=1;
 do
  {
  fx[pre[i]][i]+=fxmin;
  fx[i][pre[i]]-=fxmin;
  i=pre[i];
  }while(i!=1);
 }
void flux()
 {
 eok=true;
 while(drum)
  {
  eok=false;
  BF();
  }
 }
int main()
 {
 read();
 flux();
 g<<sol;
 return 0;
 }