#include<fstream.h>
#include<math.h>
#define infinit 32000
#define nmax 1024
long a[nmax][nmax],b[nmax][nmax],min,rez;
int n,t[nmax],c[nmax],s,f;
void cit()
{//a[i][j] -  matricea costurilor, cu a[i][j]=0 daca nu exista (i,j)
	int i,j,m;
	ifstream fin("maxflow.in");
	fin>>n>>m;
	s=1; f=n;
	while(m--)
		fin>>i>>j>>a[i][j];
	fin.close();
}
int gasire_drum()
{//Se cauta un drum in crestere cu un nr minim de arce, parcurgand graful in latime(BF)
	//c-coada iar t- vectorul tata cu t[i]=0 daca i este nevizitat
	int p,u,nodc,i;
	p=u=1; c[u]=s; t[s]=-1;
	while(p<=u)
	{
		nodc=c[p];
		for(i=1;i<=n;i++)
			if(a[nodc][i]-b[nodc][i]>0&&t[i]==0)
			{
				t[i]=nodc;
				u++; c[u]=i;
				if(i==f)
					return 1;
			}
			else
				if(b[i][nodc]>0&&t[i]==0&&i!=s)
				{
					t[i]=-nodc;
					u++; c[u]=i;
					if(i==f)
						return 1;
				}
		p++;
	}
	return 0;
}
void make_better(int nod)
{
	/*functie recursiva care imbunatateste drumul in crestere gasit 
	si memorat su ajutorul vectorului de tati t; min= capacitatea reziduala*/
	if(nod!=s)
		if(t[nod]>0)
		{
			if(a[t[nod]][nod]-b[t[nod]][nod]<min)
				min=a[t[nod]][nod]-b[t[nod]][nod];
			make_better(t[nod]);
			b[t[nod]][nod]+=min;
		}
		else
		{
			if(b[nod][abs(t[nod])]<min)
				min=b[nod][abs(t[nod])];
			make_better(abs(t[nod]));
			b[nod][abs(t[nod])]-=min;
		}
}
void afis()
{
	int i;
	ofstream fout("maxflow.out");
	fout<<rez<<'\n';
	fout.close();
}
int main()
{
	cit();
	while(gasire_drum())
	{
		min=infinit;
		make_better(f);
		rez+=min;
		for(i=1;i<=n;i++)
			t[i]=0;
	}
	afis();
	return 0;
}