#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;
int n,m,sursa,dest;
const int dim=1000+10;

vector < int > V[dim],h(dim),e(dim);
vector <  vector < int > > F(dim,vector < int > (dim,0)),C(dim,vector < int > (dim,0));
vector < vector < bool > > is(dim,vector < bool > (dim,0));

void INITIALIZER_POMPARE()
{
    for(int i=1;i<=n;i++)
    {
        h[i]=0;
        e[i]=0;
    }
    h[sursa]=n+1;
    for(int nod:V[sursa])
    {
        int flux=C[sursa][nod];
        C[sursa][nod]-=flux;
        C[nod][sursa]+=flux;  //contruim simultan graful rezidual

        F[sursa][nod]+=flux;
        F[nod][sursa]-=flux;  //actualizam fuxul pe arc

        e[nod]+=flux;
        e[sursa]-=flux;       //actualizam excedentarea
    }
}

void Pompare(int u,int v)
{
    //u este excedentar,h[u]=h[v]+1,C[u][v](in aclasi timp si cantitate reziduala) >0
    int mini=min(C[u][v],e[u]);
    C[u][v]-=mini; //iau din avut.Nu este negativ;
    C[v][u]+=mini;

    e[u]-=mini;
    e[v]+=mini;

    if(is[u][v])
    {
        F[u][v]+=mini;
        F[v][u]-=mini;
    }
    else
    {   //muchia (v,u) se afla in graful initial,iar eu parcurg muchia reziduala (u,v)
        F[v][u]+=mini;
        F[u][v]-=mini;
    }
}

void Ridicare(int u)
{
    int mini=n+1;
    for(int nod:V[u])
        if(nod!=u)
        mini=min(mini,h[nod]);

    h[u]=mini+1;
}

void Descarcare(int u)
{
    int idx=0;
    while(e[u]>0)
    {
        if(idx==V[u].size())
        {
            Ridicare(u);
            idx=0;
        }
        int v=V[u][idx];
        if(C[u][v]>0 && h[u]==h[v]+1)
        {
            Pompare(u,v);
        }
        else idx++;
    }
}

void Pompare_topologica()
{
    INITIALIZER_POMPARE();
    list < int > lista;
    list < int > ::iterator it;

    for(int i=1;i<=n;i++)
    if(i!=sursa && i!=dest)
    {
        lista.pb(i);
    }

    it=lista.begin();
    while(it!=lista.end())
    {
        int u=lista.front();
        int old_height=h[u];
        Descarcare(u);
        if(h[u]>old_height)
        {
            lista.erase(it);
            lista.push_front(u);
            it=lista.begin();
        }
        it++;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        V[a].pb(b);
        V[b].pb(a);//!! Am construit graf neorientat pentur simiiarera grafului rezidual

        C[a][b]=c;
        F[a][b]=0;
        is[a][b]=1;
    }
    sursa=1; dest=n;
    Pompare_topologica();

    int ans=0;
    for(int nod:V[sursa])
        ans+=F[sursa][nod];
    g<<ans;

    return 0;
}