#include <fstream>
#include <iostream>
#include <queue>
#define MAX 1001
#define INFINITY 0x3fffffff
#define min(x, y) (x>y?y:x)

using std::ifstream;
using std::ofstream;

int f[MAX][MAX], c[MAX][MAX], n, source, sink;

void read()
{
	int a, b, cost, m;
	ifstream fin("maxflow.in");
	fin>>n>>m;
	
	while(m--)
	{
		fin>>a>>b>>cost;
		c[a-1][b-1]=cost;
	}
	source = 0;
	sink = n-1;
	fin.close();	
}

int Edmonds_Karp(){
        int pre[MAX],que[MAX],d[MAX],p,q,t,i,j;
        if (source==sink) return INFINITY;
        
		while (true){
                memset(pre,-1,sizeof(pre));
                d[source]=INFINITY;p=q=0,que[q++]=source;
                while(p<q&&pre[sink]<0){
                        t=que[p++];
                        for (i=0;i<n;i++)
                                   if (pre[i]<0&&(j=c[t][i]-f[t][i]))
                                        pre[que[q++]=i]=t,d[i]=min(d[t],j);
                }
                if (pre[sink]<0) break;
                for (i=sink;i!=source;i=pre[i])
                                f[pre[i]][i]+=d[sink],f[i][pre[i]]-=d[sink];
        }
        for (j=i=0;i<n;j+=f[source][i++]);
        return j;
}

void show()
{
	ofstream fout("maxflow.out");
	fout<<Edmonds_Karp()<<"\n";
	fout.close();
}


int main ()
{
	read();
	
	show();
	return 0;
}