#include <bits/stdc++.h>
#include <iostream>

using namespace std;

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

int N,M;
int capacitati[1005][1005], flux[1005][1005];
// daca e capacitate pe x y inseama ca e arc orientat x y
int graf[1005][1005]; //graf rezidual
vector<int>adiacenta[1005];
vector<bool>vizitat;
int parinte[1005];//pt bfs
vector<bool> sursa;//pt dfs1
vector<bool> dest;//pt dfs2
vector<int> rez;

int cardinal[1005][1005];

bool BFS(int s)
{

    vizitat.assign(N+1, false);
    int nod;

    for(int i = 1; i <= N; i++)
        parinte[i] = 0;

    queue <int> q;
    q.push(s);
    vizitat[s] = true;

    parinte[s] = s;

    while(!q.empty())
    {
        //cat timp coada nu e vida vad daca gasesc un vecin pt nodul din fata cozii
        nod = q.front();
        q.pop();

        for(auto i:adiacenta[nod])//for(int i = 1; i <=n+m+1; i++)
        {
            if(!vizitat[i] &&  capacitati[nod][i] > flux[nod][i])//daca mai pot folosi aceea muchie adica daca se mai poate adauga flux pe ea
            {
                vizitat[i] = true;
                parinte[i] = nod;

                if(i == N)
                    return true;


                q.push(i);

            }
        }
    }

    if(vizitat[N] == true)
        return true; //daca am vizitat si nodul destinatie inseamna ca am gasit drum de la sursa la el

    return false;



}


void Ford_Fulkerson()
{
    int cap_reziduala;
    int flux_maxim = 0;
    /*cout<<BFS(1);
    for(auto i : vizitat)
            cout<<i<<" ";*/

    while(BFS(1))
    {

        //cout<<"yes ";
        for(auto vecin : adiacenta[N])
        {

            if(flux[vecin][N] != capacitati[vecin][N] && vizitat[vecin])
            {
                parinte[N] = vecin;
                cap_reziduala = 2e9;

                int j = N;
                while(j!=1)
                {
                    if(cap_reziduala > capacitati[parinte[j]][j] - flux[parinte[j]][j])
                        cap_reziduala = capacitati[parinte[j]][j] - flux[parinte[j]][j];
                    j = parinte[j];
                }


                        flux_maxim += cap_reziduala;

                //cout<<cap_reziduala<<" ";

                j = N;
                while(j!=1)
                {
                    flux[parinte[j]][j] += cap_reziduala;//pe arcul direct adaug fluxul
                    flux[j][parinte[j]] -= cap_reziduala;//pe arcul indirect scad fluxul
                    j = parinte[j];
                }

            }



        }


    }
   out<<flux_maxim<<"\n";
}

int main()
{
    //nu se mai apeleaza BFS in ford-fulkerson de fiecare data ci se construieste arborele bfs dupa o parcurgere

    int x,y,cost;
    in>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        in>>x>>y>>cost;
        cardinal[x][y] = cardinal[y][x] = i;

        adiacenta[x].push_back(y);
        capacitati[x][y] = cost;

        adiacenta[y].push_back(x);
        capacitati[y][x] = cost;

    }




    Ford_Fulkerson();


return 0;
}