#include<fstream>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
int n,m,s,d; // s=nodul sursa | d=nodul destinatie
int C[1010][1010]; // capacitatea fiecarui arc
int F[1010][1010]; // fluxul fiecarui arc
int vizitat[1010]; // in acest vector vom marca nodurile
int *G[1010];
int sol; //fluxul maxim


void Citire()
{
	int i,x,y,c;
	ifstream fin("maxflow.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		G[i]=(int *)realloc(G[i],sizeof(int));
		G[i][0]=0;
	}
	s=1;
	d=n;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		C[x][y]=c;
		G[x][0]++;
		G[x]=(int *)realloc(G[x],(G[x][0]+1)*sizeof(int));
		G[x][G[x][0]]=y;
		G[y][0]++;
		G[y]=(int *)realloc(G[y],(G[y][0]+1)*sizeof(int));
		G[y][G[y][0]]=x;
	}
	fin.close();
}

int BFS()
{
	//returneaza 1 daca nodul destinatie nu a fost marcat
	int i,x;
	queue <int> Q;
	Q.push(s);
	vizitat[s]=1;
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		for(i=1;i<=G[x][0];i++)
		{
			if(vizitat[G[x][i]]==0)
			{
				if(F[x][G[x][i]]<C[x][G[x][i]])
				{
					vizitat[G[x][i]]=x;
					Q.push(G[x][i]);
				}
				/*else
					if(F[G[x][i]][x]>0)
					{
						vizitat[G[x][i]]=-x;
						Q.push(G[x][i]);
					}*/
			}
		}
	}
	if(vizitat[d]==0)
		return 1;
	return 0;
}

void Edmonds_Karp()
{
	int i,v,x;
	do
	{
		//marcam nodurile printr-o parcurgere BFS
		for(i=0;i<=n;i++)
			vizitat[i]=0;
		if(BFS()==1) //daca nodul destinatie nu a fost marcat am gasit fluxul maxim
			return;
		for(i=1;i<=G[d][0];i++)
		{
			x=G[d][i];
			if(F[x][d]<C[x][d] && vizitat[x])
			{
				v=C[x][d]-F[x][d];
				while(x!=s)
				{
					v=min(v,C[vizitat[x]][x]-F[vizitat[x]][x]);
					x=vizitat[x];
				}
				x=G[d][i];
				F[x][d]+=v;
				F[d][x]-=v;
				while(x!=s)
				{
					F[vizitat[x]][x]+=v;
					F[x][vizitat[x]]-=v;
					x=vizitat[x];
				}
				sol+=v;
			}
		}
	}
	while(1);
}

void Afisare()
{
	ofstream fout("maxflow.out");
	fout<<sol<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Edmonds_Karp();
	Afisare();
	return 0;
}