#include <bits/stdc++.h>

using namespace std;

class Graf
{
protected:
    int n, m;
    ///structuri de retinere a muchiilor
    vector<vector<int>> muchii; //liste de adiacenta- array de vectori
    vector<tuple<int,int,int>> muchii_costuri_lista; //array de muchii cu costuri (e1,e2,cost)
    vector<vector<pair<int,int>>> muchii_costuri_adiacenta; //liste de adiacenta- array de vectori pentru muchii cu costuri (nod,cost)
    vector<vector<int>> matrice_ponderi;

public:
    Graf(int noduri, int muchii):n(noduri), m(muchii) {}

};


class GrafOrientat: public Graf
{
private:
    bool ExistaLantNesaturat(int s,int d, vector<int>& tata, vector<vector<int>>& muchii,
                             vector<vector<int>>& c, vector<vector<int>>& f, vector<int>& viz);

public:
    GrafOrientat(int noduri, int muchii):Graf(noduri,muchii) {}
    void CitireMuchiiCosturiAdiacenta(ifstream& fin);
    int FluxMaxim(int s, int d);
};
void GrafOrientat::CitireMuchiiCosturiAdiacenta(ifstream& fin)
{
    int n1,n2,c;
    muchii_costuri_adiacenta.resize(n+1);

    for(int i=0; i<m; ++i)
    {
        fin>>n1>>n2>>c;
        muchii_costuri_adiacenta[n1].push_back(make_pair(n2,c));
    }
}

bool GrafOrientat::ExistaLantNesaturat(int s,int d, vector<int>& tata, vector<vector<int>>& muchii,
                                       vector<vector<int>>& c, vector<vector<int>>& f, vector<int>& viz)
{
    queue<int> C;

    viz.clear();
    viz.resize(n+1,0);

    C.push(s);
    viz[s]=1;
    tata[d]=0;

    //construiesc drum pana la d
    while(!C.empty() && tata[d]==0)
    {
        int v=C.front();
        C.pop();

        for(int i=0; i<(int)muchii[v].size(); ++i)
        {
            int vecin=muchii[v][i];

            if(!viz[vecin] && c[v][vecin]>f[v][vecin])
            {
                C.push(vecin);
                viz[vecin]=1;
                tata[vecin]=v;
            }
        }
    }

    if(tata[d])
        return true; //exista drum pentru ca destinatia are un tata
    else
        return false;
}

int GrafOrientat::FluxMaxim(int s, int d)
{
    ///algoritmul Ford-Fulkerson
    vector<int> tata;
    vector<vector<int>> muchii; //consider graful neorientat
    vector<vector<int>> c; //matrice capacitate
    vector<vector<int>> f; //matrice flux
    vector<int> viz; //pentru a retine nodurile vizitate in bfs
    int flux_total=0;

    muchii.resize(n+1);
    tata.resize(n+1,0);
    c.resize(n+1,vector<int>(n+1,0));
    f.resize(n+1,vector<int>(n+1,0));

    //initializare (muchii, capacitate)
    for(int i=1; i<=n; ++i)
        for(int j=0; j<(int)muchii_costuri_adiacenta[i].size(); ++j)
        {
            int nod=get<0>(muchii_costuri_adiacenta[i][j]);
            int cost=get<1>(muchii_costuri_adiacenta[i][j]);
            muchii[i].push_back(nod);
            muchii[nod].push_back(i);
            c[i][nod]=cost;
        }

    while(ExistaLantNesaturat(s,d,tata,muchii,c,f,viz))
    {
        //iau toate drumurile care intra in d
        for(int i=0; i<(int)muchii[d].size(); ++i)
        {
            int v=muchii[d][i];
            if(f[v][d]!=c[v][d] && viz[v]) //muchie valida
            {
                tata[d]=v;
                int val_minima=110005;//un numar suficient de mare

                //aflu cu cat pot modifica fluxul pe drumul de la s la d (pornind din d) => capacitatile reziduale
                for (int i=d; i!=s; i=tata[i])
                    if(c[tata[i]][i]-f[tata[i]][i]<val_minima)
                        val_minima=c[tata[i]][i]-f[tata[i]][i];

                if(val_minima!=0)
                    //parcurg din nou drumul pentru a actualiza fluxurile
                {
                    for (int i=d; i!=s; i=tata[i])
                    {
                        f[tata[i]][i]+=val_minima;
                        f[i][tata[i]]-=val_minima;
                    }
                    flux_total+=val_minima; //actualizez fluxul final
                }
            }
        }
    }

    return flux_total;
}

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

    int n,m;
    fin>>n>>m;
    GrafOrientat g(n,m);
    g.CitireMuchiiCosturiAdiacenta(fin);

    fout<<g.FluxMaxim(1,n);

    fin.close();
    fout.close();
}

int main()
{
    PbFluxMaxim();

    return 0;
}