#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,n,m,sursa,dest;
const int dim=1e3+10;

struct edge{
    int cap;
    int flow;
};

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

void initializare_preflux(int n)
{
    for(int i=0;i<=n;i++)
    {
        h[i]=0;
        e[i]=0;
    }
    h[sursa]=n;
    for(int nod:V[sursa])
    {
        e[nod]=C[sursa][nod].cap;
        C[nod][sursa].cap=e[nod];
        C[sursa][nod].flow=e[nod];
        C[nod][sursa].flow=-e[nod];
        e[sursa]-=e[nod];
    }
}

void Pompare(int u,int v)
{
    int mini=min(e[u],C[u][v].cap);
    C[u][v].cap-=mini;
    C[v][u].cap+=mini;
    if(is[u][v]==1)
    {
        C[u][v].flow+=mini;
        C[v][u].flow-=mini;
    }
    else
    {
        C[u][v].flow-=mini;
        C[v][u].flow+=mini;
    }
    e[u]-=mini;
    e[v]+=mini;
}

void Ridicare(int u)
{
    int mini=n;
    for(int nod:V[u])
        if(C[u][nod].cap>0)
            mini=min(mini,h[nod]);
    h[u]++;
}

void Descarcare(int u) {

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

void pompare_topologica(int n)
{
    initializare_preflux(n);
    vector < int > lista;
    for(int i=1;i<=n;i++)
        if(i!=sursa && i!=dest) lista.push_back(i);
    int idx=0;
    while(idx<lista.size())
    {
        int u=lista[idx];
        int old=h[u];
        Descarcare(u);
        if(h[u]>old)
        {
            lista.erase(lista.begin()+idx);
            lista.insert(lista.begin(),u);
            idx=0;
        }
        idx++;
    }
}

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);

        C[a][b]={c,0};
        C[b][a].flow=0;
        is[a][b]=1;
    }
    sursa=1;dest=n;
    pompare_topologica(n);
    g<<e[dest];

    return 0;
}