#include <bits/stdc++.h>
#define INF 2000000000
#define VMAX 1005
#define NMAX 5005
using namespace std;
ifstream fin ("maxflow.in");
ofstream fout ("maxflow.out");

int flux_pe_muchie[NMAX];
bool vizitat[VMAX];
queue<int> noduri_vizitate_in_parcurgere;
vector<int> noduri_finale_vizitate_in_parcurgere;
int n;

vector<int> graf[VMAX];
// cat flux merge prin muchie si limita


int capacitate[VMAX][VMAX];
int flux[VMAX][VMAX];
int tata[VMAX]; // arborele bfs pe care il vom parcurge de la sink la sursa ptr a adauga cost


int dfs(int nod, int minim) // minim repr cat flux avem de distribuit prin muchiile din nodul nod
{
    int flux_total = 0;
    if(nod == n) // am ajuns la sink
        return minim;
    vizitat[nod]=1;
    noduri_vizitate_in_parcurgere.push(nod);


    for(auto i:graf[nod])
    {
        if(vizitat[i])
            continue;
        if(capacitate[nod][i]==0 && flux[nod][i]<0) // muchie inversa si avem de unde intoarce flux
        {
            int nr = dfs(i,min(minim,-flux[nod][i])); // cat flux a incaput prin acel path
            if(nr)
            {
                flux[nod][i]+=nr;
                flux[i][nod]-=nr;
                flux_total+=nr;
                minim-=nr;
            }
        }
        else if(capacitate[nod][i]>0 && capacitate[nod][i]-flux[nod][i]>0) // muchie normala si avem unde adauga flux
        {
            int nr = dfs(i,min(minim,capacitate[nod][i]-flux[nod][i])); // cat flux a incaput prin acel path
            if(nr)
            {
                flux[nod][i]+=nr;
                flux[i][nod]-=nr;
                flux_total+=nr;
                minim-=nr;
            }
        }
    }

    return flux_total;
}


int bfs(int nod)
{
    queue<int> q;
    q.push(nod);
    while(!q.empty())
    {
        nod = q.front();
        q.pop();
        vizitat[nod]=1;

        for(auto i:graf[nod])
        {
            if(vizitat[i]==0 && capacitate[nod][i]-flux[nod][i]>0) // nu am mai mers prin i si mai incape flux
            {
                if(i==n) // i == sink
                {
                    noduri_finale_vizitate_in_parcurgere.push_back(nod);
                    continue;
                }
                tata[i]=nod; // tatal nodului i in arbore va fi nod
                q.push(i);
            }
        }
    }
}


int main()
{
    long long int m,i,j,k,t,q,nr,maxim,nod,max_flow,flow_adg;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>j>>k>>t;
        capacitate[j][k]+=t;
        graf[j].push_back(k);
        graf[k].push_back(j);
    }

    max_flow=0;
    //while(nr=dfs(1,INF))
    //{
    //    max_flow+=nr;
    //    while(!noduri_vizitate_in_parcurgere.empty())
    //    {
    //        vizitat[noduri_vizitate_in_parcurgere.front()]=0;
    //        noduri_vizitate_in_parcurgere.pop();
    //    }
    //}
    do
    {
        bfs(1);
        flow_adg=0;
        for(auto i:noduri_finale_vizitate_in_parcurgere)
        {
            maxim = capacitate[i][n]-flux[i][n]; // maximul pe care il putem adg
            nod=i;
            while(tata[nod]!=0) // mereu lantul va ajunge pana la sursa
            {
                maxim=min((int)maxim,capacitate[tata[nod]][nod]-flux[tata[nod]][nod]);
                nod=tata[nod];
            }
            // putem mari intregul lant cu valoarea "maxim"
            flux[i][n]+=maxim;
            flux[n][i]-=maxim;
            nod=i;
            while(tata[nod]!=0) // refacem lantul, care va fi acelasi pentru ca graful bfs este de tip arbore
            {
                flux[tata[nod]][nod]+=maxim;
                flux[nod][tata[nod]]-=maxim;
                nod=tata[nod];
            }
            flow_adg+=maxim;
        }
        max_flow+=flow_adg;
        for(i=1;i<=n;i++)
            vizitat[i]=tata[i]=0;
        noduri_finale_vizitate_in_parcurgere.clear();
    }
    while(flow_adg);


    fout<<max_flow<<'\n';



    return 0;
}