#include<fstream>
using namespace std;
#define N 1002
int cap[N][N],flux[N][N];
int n,m,x,y,c,i,inf=100000000;
int Q[N],t[N];
struct nod{int info;nod*adr;}*v[1002],*p;
int bfs(int s,int d)
{int i,p,u,nd;
  p=u=1; Q[1]=s;
  for(i=0;i<=n;i++)t[i]=0;
  t[s]=1;
	while(p<=u)
	{
		nd=Q[p++];
		nod*q=v[nd];
		while(q)
		{
		 if(cap[nd][q->info]>flux[nd][q->info])
		  if(!t[q->info])
		  {
			t[q->info]=nd;
			Q[++u]=q->info;
		  }
		  q=q->adr;
		}
	}
	return t[d];
}
int dinic(int s,int d)
{int flow=0,minn,i,j;
	while(bfs(s,d))
	{
		nod*q=v[d];
	  while(q)
	  {
	   if(cap[q->info][d]>flux[q->info][d])
	   {
		minn=cap[q->info][d]-flux[q->info][d];
		 for(i=q->info;i!=s;i=t[i])
			minn=min(minn,cap[t[i]][i]-flux[t[i]][i]);
		 
		  flux[q->info][d]+=minn;
		  flux[d][q->info]-=minn;
		 for(i=q->info;i!=s;i=t[i])
		  flux[t[i]][i]+=minn,
		  flux[i][t[i]]-=minn;

		 flow+=minn;
	   }
	   q=q->adr;
	  }
	}
	return flow;
}
int main()//flux cu liste pt BFS mai rapid
{
	ifstream f("maxflow.in");ofstream g("maxflow.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		cap[x][y]=c;
		p=new nod;
		p->info=y; p->adr=v[x]; v[x]=p;
		p=new nod;
		p->info=x; p->adr=v[y]; v[y]=p;
	}
	g<<dinic(1,n);
	f.close();g.close();
return 0;}