#include<fstream>
#include<cmath>
using namespace std;
int n,m,x,y,z,t[1001][1001],u[1001][1001],ok=1,bfs[1001],mark[1001],s;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
void amel(int x)
{int Min=t[x][n]-u[x][n],aux=x;
while(aux!=1)
{if(mark[aux]>0)
Min=min(Min,t[mark[aux]][aux]-u[mark[aux]][aux]);
else
Min=min(Min,u[aux][-mark[aux]]);
aux=abs(mark[aux]);
}
u[x][n]+=Min;
aux=x;
while(aux!=1)
{if(mark[aux]>0)
u[mark[aux]][aux]+=Min;
else
u[aux][-mark[aux]]-=Min;
aux=abs(mark[aux]);
}
}
void lda()
{bfs[0]=1;
bfs[1]=1;
for(int j=1;j<=bfs[0];j++)
for(int k=2;k<n;k++)
{if(!mark[k]&&u[bfs[j]][k]<t[bfs[j]][k])
{mark[k]=bfs[j];
bfs[++bfs[0]]=k;
}
if(!mark[k]&&u[k][bfs[j]]>0)
{mark[k]=-bfs[j];
bfs[++bfs[0]]=k;
}
}
ok=0;
for(int j=1;j<n;j++)
if(mark[j]&&u[j][n]<t[j][n])
{ok=1;
amel(j);
}
for(int j=2;j<n;j++)
mark[j]=0;
}
int main()
{f>>n>>m;
for(int i=1;i<=m;i++)
{f>>x>>y>>z;
t[x][y]=z;
}
while(ok)
lda();
for(int i=2;i<=n;i++)
s+=u[1][i];
g<<s;
return 0;
}