#include<fstream>
#define N 1002
#define oo 10000000
using namespace std;
int cap[N][N],flux[N][N];//l=land de la destinatie la sursa
int n,m,x,y,c,i,t[N];
short viz[1002];
ofstream g("maxflow.out");
int bfs(int sursa,int dest)
{
	int Q[N + 1], p = 0, q = 0;
	bool use[N];
	for(int i=0;i<=N;i++)t[i]=use[i]=0;
	Q[0] = sursa;
	use[sursa] = 1;
	
	while(p<=q) 
	{
		int u=Q[p++];
	 for(int i=sursa;i<=dest;++i) // pt fiecare nod ( adiacent )
		if(!use[i]) // nu am folosit nodul
		  if(cap[u][i]-flux[u][i]>0) // mai putem pompa?
		  {
			Q[++q] = i; // inseram nodul i in coada
			t[i] = u;  
			use[i] = 1; 
		  }
	}
	return t[dest];
}

void dinic(int sursa, int dest)//calculeaza mai multe drumuri de ameliorare cu 1 singur bfs
{
	long flow=0;
	long i,min,j;
	
	while(bfs(sursa,dest)) // cat timp mai exista un drum de ameliorare
	{
	  for(j=sursa;j<dest;++j)
	   if(cap[j][dest]-flux[j][dest]>0)//ia nodurile din care se poate ajunge la destinatie
	   {
		min=oo;
			
		if(cap[j][dest]-flux[j][dest]<min) min=cap[j][dest]-flux[j][dest];
			
		for(i=j; i!=sursa; i=t[i])
			if(cap[t[i]][i]-flux[t[i]][i] < min) min=cap[t[i]][i]-flux[t[i]][i];
 //calculam minimul dintre capacitatile de pe drum
		
		if(min == oo) continue;
			
		flux[j][dest]+=min;
		flux[dest][j]-=min;
			
		for(i=j ; i!=sursa; i=t[i]) 
			flux[t[i]][i]+=min, //adaugam minimul la fluxul de pe arcele de pe drum
			flux[i][t[i]]-=min; //scadem minimul de pe arcele inverse
		
		flow+=min; // adaugam minimul la flux
	   }
	}
 g<<flow;
}

int main()
{
	ifstream f("maxflow.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		cap[x][y]=c;
	}
	dinic(1,n);//edmonds-karp
	f.close();g.close();
return 0;}