#include <iostream>
#include <fstream>
#include <queue>

/*
O retea de transport este un graf orientat in care fiecare muchie are asociata o capacitate si o anumita cantitate de flux.
Fluxul primit de fiecare muchie trebuie sa fie mai mic sau egal decat capacitatea acesteia. De asemenea, pentru fiecare nod,
fluxul care intra in nod trebuie sa fie egal cu cantitatea de flux care iese din nod. Cu alte cuvinte, suma fluxurilor asociate
muchiilor care intra intr-un nod trebuie sa fie egala cu suma fluxurilor asociate muchiilor care ies din nod, exceptie facand
nodurile speciale S si D, denumite sursa, respectiv, destinatie. Din nodul sursa poate doar iesi flux, in timp ce in nodul destinatie
poate doar intra flux. Valoarea fluxului unei astfel retele este egal cu suma fluxului care iese din sursa sau cu suma fluxului
care intra in destinatie (cele doua fluxuri sunt egale).
Dandu-se o retea de transport, in care initial fluxul pe fiecare muchie este 0,
sa se calculeze fluxul maxim care poate fi trimis prin aceasta retea.

*/
using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int bf(int s, int n, vector<int> *la, long **f, long **cost, long **rezid, int *tata, int *viz){
    int i,x;
    for(i=0;i<=n;i++)
    	viz[i]=tata[i]=0;
    queue<int> c;

    c.push(s);
    viz[s]=1;
    while(c.size()>0){
        x=c.front();
        c.pop();
        for(i=0;i<la[x].size();i++){
            int y=la[x][i];
            if(viz[y]==0 && rezid[x][y]>0){
                tata[y]=x;
                if(y==n)
                    return 1;
                c.push(y);
                viz[y]=1;
            }
        }

    }
    return 0;
}

int main(){
	int n,m,i,j;
	vector<int> *la;
	vector<int> *larezid;


    long **f,**cost,**rezid;

    int x,y;
    long c,c_max;
    //l -liste de adiacenta pentru graful rezidual
    //linit - liste de adiacenta pentru graful initial
    fin>>n>>m;
    la=new vector<int>[n+1];
    larezid=new vector<int>[n+1];

    f=new long*[n+1];
    cost=new long*[n+1];
    rezid=new long*[n+1];
	for(i=0;i<=n;i++){
		f[i]=new long[n+1];
		cost[i]=new long[n+1];
		rezid[i]=new long[n+1];
	}

	for(i=0;i<=n;i++)
		for(j=0;j<=n;j++)
			f[i][j]=cost[i][j]=rezid[i][j]=0;


    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        la[x].push_back(y);
        larezid[x].push_back(y);
        larezid[y].push_back(x); //arc invers in graful rezidual

		rezid[x][y]=c;
		rezid[y][x]=0;//pe y,x capacitatea este 0

		if (c>c_max)
        	c_max=c;
    }

    fin.close();
    int *tata=new int[n+1];
    int *viz=new int[n+1];

    long fmax=0;
    int s=1;//sursa
    int t=n;//destinatia

    while(bf(s,n,larezid,f,cost,rezid,tata,viz)){
		//calculam i(P) = capacitatea reziduala minima pe un arc de pe drumul de la s la t determinat cu bf
        long iP=c_max; //i(P)
        t=n;
        //fout<<"drumul: ";
        while(t!=s)  {
        	//fout<<t<<" ";
            if(iP>rezid[tata[t]][t])
                iP= rezid[tata[t]][t];
            t=tata[t];
        }
        /*fout<<s<<" ";
        fout<<" capacitate "<<iP<<endl;*/
          //revizuim fluxul de-a lungul lantului determinat
        t=n;
        while(t!=s)  {
            rezid[tata[t]][t]-=iP;
            rezid[t][tata[t]]+=iP;
            t=tata[t];
        }
        fmax+=iP; //creste valoarea fluxului cu iP

    }
    fout<<fmax<<endl;
    /*fout<<"un flux maxim: "<<endl;

    for(int u=1;u<=n;u++)
    	for(j=0;j<la[u].size();j++){
    		int v=la[u][j];
       			fout<<"arcul "<<u<<" "<<v<<" flux "<<rezid[v][u]<<endl;
		}
    */
    fout.close();
    return 0;
}