# include <fstream>
# include <vector>
# include <queue>
# define NMAX 1010
# define INF 2000000000

using namespace std;

ifstream fin ("maxflow.in");
ofstream fout ("maxflow.out");
int n,m,i,j,sum;
int pom[NMAX],pre[NMAX],dif[NMAX];
queue <int> Q;
vector <int> G[NMAX];
vector <int> C[NMAX];
vector <int> F[NMAX];

void BFS ()
{
	int x,j,y;
	Q.push(1);
	pom[1]=INF; dif[1]=INF;
	while (!Q.empty())
	{
		x=Q.front();
		Q.pop();
		for (j=1;j<=G[x][0];j++)
		{
			y=G[x][j];
			if (!pom[y])
			{
				if (C[x][j]>0&&C[x][j]-F[x][j]!=0)
				{
					Q.push(y);
					pom[y]=j;
					pre[y]=x;
					dif[y]=dif[x];
					if (C[x][j]-F[x][j]<dif[y])
						dif[y]=C[x][j]-F[x][j];
				}
				else
				if (C[x][j]<0&&F[x][j]!=0)
				{
					Q.push(y);
					pom[y]=j;
					pre[y]=-x;
					dif[y]=dif[x];
					if (F[x][j]<dif[y])
						dif[y]=F[x][j];
				}
			}
		}
	}
}

int main ()
{
	//citire
	int x,y,c;
	fin>> n>> m;
	for (i=1;i<=n;i++)
		{G[i].push_back(0);C[i].push_back(0);F[i].push_back(0);}
	for (i=1;i<=m;i++)
	{
		fin >> x>>y>>c;
		G[x][0]++;
		G[y][0]++;
		C[x].push_back(c);
		C[y].push_back(-c);
		G[x].push_back(y);
		G[y].push_back(x);
		F[x].push_back(0);
		F[y].push_back(0);
	}
	BFS();
	while (pom[n])
	{
		x=n;
		while (pom[x]!=INF)
		{
			y=pom[x];
			if (pre[x]<0)
			{
				
			F[-pre[x]][y]-=dif[n];
			x=-pre[x];
			}
			else
			{
			F[pre[x]][y]+=dif[n];
			x=pre[x];
			}
		}
		for(i=1;i<=n;i++)
			dif[i]=0,pom[i]=0;
		BFS();
	}
	sum=0;
	for (i=1;i<=G[1][0];i++)
		sum+=F[1][i];
	fout<<sum<<'\n';
	fin.close();
	fout.close();
	return 0;
}