#include <bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

const int DN=1005;
int n,m,f,g,s,d,dim,flow[DN][DN],c[DN][DN],cnt;
int h[DN],sol[DN],vecin[DN];
deque<int>v[DN],z;

void pompare(int f,int g)
{
    int val=min(c[f][g]-flow[f][g],sol[f]);
    sol[f]-=val;
    sol[g]+=val;
    flow[f][g]+=val;
    flow[g][f]-=val;
}

int inaltare(int nod)
{
    cnt++;
    int mi=n+1;
    if(v[nod].size()==0)
        return 0;
    for(auto i:v[nod])
        if(c[nod][i]-flow[nod][i]>0)
            mi=min(mi,h[i]);
    if(mi==n+1||mi<h[nod])
        return 0;
    h[nod]=mi+1;
    return 1;
}

void descarc(int nod)
{
    while(sol[nod]>0)
    {
        for(auto i:v[nod])
            if((i==d||h[nod]==h[i]+1)&&c[nod][i]-flow[nod][i]>0)
                pompare(nod,i);

        if(!inaltare(nod))
            break;
    }
}

void solve()
{
    //cout<<z.size()<<'\n';
    for(int i=1;i<=n;i++)
    {
        if(i==s||i==d)
            continue;
        vecin[i]=v[i].size();
        //cout<<i<<'\n';
        z.push_back(i);
    }
    //cout<<z.size()<<'\n';
    int pz=0;
    while(pz<z.size()&&cnt<1e4)
    {
        //return;
        int nod=z[pz];
        //cout<<pz<<' '<<nod<<' '<<sol[nod]<<' '<<sol[3]<<'\n';
        int lst=h[nod];
        descarc(nod);
        if(h[nod]>lst)
        {
            z.erase(z.begin()+pz);
            z.push_front(nod);
            pz=0;
        }
        pz++;
    }
}

int main()
{
    fin>>n>>m;
    s=1;
    d=n;
    for(int i=1;i<=m;i++)
    {
        fin>>f>>g>>dim;
        c[f][g]=dim;
        if(f!=d&&g!=s)
            v[f].push_back(g);
        if(f!=s&&g!=d)
            v[g].push_back(f);
    }
    for(auto i:v[s])
        sol[i]+=c[s][i];
    solve();
    cout<<sol[d];
    fout<<sol[d];
}