#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int N,M,sol,ap[1010];
vector< pair<int,int> > A[1010];
struct matrix
{
	int flux,cap;
};
matrix a[1010][1010];

inline int getmin(int x1,int x2,int sens)
{
	if(sens>0)
	{
		return a[x1][x2].cap-a[x1][x2].flux;
	}
	return a[x1][x2].flux;
}

inline int DFs(int nod,int mn)
{
	int sum=0;
	//cout<<"Minimul in "<<nod<<" este "<<mn<<'\n';
	if(nod==N)
	{
		sol=sol+mn;
		return mn;
	}
	
	for(vector< pair<int,int> >::iterator it=A[nod].begin();it!=A[nod].end();++it)
	{
		if(!ap[it->first])
		{
			ap[it->first]=1;
			if(nod==1) sum=0;
			cout<<"Intra in "<<it->first<<" cu minim "<<max(0,min(getmin(nod,it->first,it->second),mn)-sum)<<'\n';
			sum+=DFs(it->first,max(0,min(getmin(nod,it->first,it->second),mn)-sum));
			cout<<"Iese din "<<it->first<<" cu minim "<<max(0,min(getmin(nod,it->first,it->second),mn)-sum)<<'\n';
			ap[it->first]=0;
			if(it->second>0)
			{
				a[nod][it->first].flux+=sum;
				a[it->first][nod].flux+=sum;
			}
			else
			{
				a[nod][it->first].flux-=sum;
				a[it->first][nod].flux-=sum;
			}
		}
	}
}


int main()
{
	ifstream in("maxflow.in");
	ofstream out("maxflow.out");
	
	in>>N>>M;
	for(int i=1;i<=M;++i)
	{
		int x1,x2,cost;
		in>>x1>>x2>>cost;
		A[x1].push_back(make_pair(x2,+1));
		A[x2].push_back(make_pair(x1,-1));
		a[x1][x2].cap=a[x2][x1].cap=cost;
	}
	
	ap[1]=1;
	DFs(1,2000000000);
	
	out<<sol<<'\n';
	out.close();
	return 0;
}