#include <fstream>
#include <vector>
#define inf 2147000000
using namespace std;

struct s_node
{
vector <int> ad;
};

int n,m;
int cap[1001][1001];
int flow[1001][1001];
int global[10001];
bool repeat[1001];
s_node node[1001];
int max_flow;
bool sens_neg;

//void tipar(int nivel);
void flow_increase(int nivel);
bool valid(int nivel);
void back(int nivel);

int main()
{
ifstream in("maxflow.in");
ofstream out("maxflow.out");

int i1;
int x,y,z;

in>>n>>m;
for(i1=0;i1<m;i1++)
	{
	in>>x>>y>>z;
	node[x].ad.push_back(y);
	node[y].ad.push_back(x);
	cap[x][y] = z;
	}
global[1] = 1; repeat[1] = true;
back(2);
sens_neg = true;
/*back(2);*/

int i2;
/*
printf("  ");
for(i1=1;i1<n+1;i1++)
	printf("%d ",i1);
printf("\n");
for(i1=1;i1<n+1;i1++)
	{
	printf("%d ",i1);
	for(i2=1;i2<n+1;i2++)
		printf("%d ",cap[i1][i2]);
	printf("\n");
	}

printf("\n\n");
printf("  ");
for(i1=1;i1<n+1;i1++)
	printf("%d ",i1);
printf("\n");
for(i1=1;i1<n+1;i1++)
	{
	printf("%d ",i1);
	for(i2=1;i2<n+1;i2++)
		printf("%d ",flow[i1][i2]);
	printf("\n");
	}*/
for(i1=1;i1<n+1;i1++)
	max_flow += flow[i1][n];

out<<max_flow;

in.close();
out.close();
return 0;
}

void back(int nivel)
{
vector <int>::iterator it1;
for(it1 = node[global[nivel-1]].ad.begin();
		it1 != node[global[nivel-1]].ad.end();
		it1++)
		{
		if(repeat[*it1])
			continue;
			
		global[nivel] = *it1;
		repeat[*it1] = true;
		if(valid(nivel))
			{
			if(global[nivel] == n)
				flow_increase(nivel);
			else if(!node[global[nivel]].ad.empty())
				back(nivel+1);
			}
		repeat[*it1] = false;
		}
}

bool valid(int nivel)
{
if(!sens_neg)
	if(!cap[global[nivel-1]][global[nivel]])
		return false;
if(cap[global[nivel-1]][global[nivel]]) //sens pozitiv
	if(flow[global[nivel-1]][global[nivel]] == cap[global[nivel-1]][global[nivel]]) //capacitate maxima
		return false;
return true;
}

void flow_increase(int nivel)
{
int i1,max_increase = inf;
for(i1=1;i1<nivel+1;i1++)
	if(cap[global[i1-1]][global[i1]]) //sens pozitiv
		if(cap[global[i1-1]][global[i1]] - flow[global[i1-1]][global[i1]] < max_increase) //daca putem creste
			max_increase = cap[global[i1-1]][global[i1]] - flow[global[i1-1]][global[i1]]; //crestem
for(i1=1;i1<nivel+1;i1++)
	if(cap[global[i1-1]][global[i1]]) // sens pozitiv
		{
		flow[global[i1-1]][global[i1]] += max_increase; //trimitem flux in sens pozitiv;
		}
	/*if(sens_neg)
		if(cap[global[i1]][global[i1-1]]) //sens negativ
			{
			flow[global[i1-1]][global[i1]] -= max_increase;
			total -= max_increase;
			}*/
//if(total>0)
//	max_flow += total;
//trebuie considerat pe sens negativ
}

/*void tipar(int nivel)
{
int i1;
for(i1=1;i1<nivel+1;i1++)
	printf("%d ",global[i1]);
printf("\n");
}*/