#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n,m,minn,s,d,x,y,ok,cost,flux,st[1005],a[1005][1005],c[1005][1005];
void afisare(int k)
{
    for(int i=1;i<=k;i++)
    {
        cout<<st[i]<<" ";
    }
    cout<<" -> "<<minn<<"\n";
    /*cout<<ok<<"\n";
    for(int i=1;i<k;i++)
    {
        cout<<c[st[i]][st[i+1]]<<" ";
    }
    cout<<"\n\n";*/
}
void valid(int k)
{
    minn=1000000;
    for(int i=1;i<k;i++)
    {
        if(c[st[i]][st[i+1]]<minn)
        {
            minn=c[st[i]][st[i+1]];
        }
    }
    if(minn!=0 && minn!=1000000)
    {
        ok=1;
        for(int i=1;i<k;i++)
        {
            c[st[i]][st[i+1]]-=minn;
        }
        flux=flux+minn;
    }
}
int OK(int k)
{
    if(a[st[k-1]][st[k]]!=1)
        return 0;
    else
        for(int i=1;i<k;i++)
            if(st[k]==st[i])
                return 0;
    return 1;
}
void back(int k)
{
    for(int i=1;i<=n;i++)
    {
        st[k]=i;
        if(OK(k))
        {
            if(st[k]==d)
            {
                ok=0;
                valid(k);
                /*if(ok==1)
                {
                    afisare(k);
                }*/
            }
            else
                back(k+1);
        }
    }
}
int main()
{
    fin>>n>>m;
    s=1;
    d=n;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        a[x][y]=1;
        c[x][y]=cost;
    }
    ok=0;
    st[1]=s;
    back(2);
    fout<<flux;
    fin.close();
    fout.close();
    return 0;
}
/*
 7 9 6 7
 6 1 2
 6 4 9
 1 2 4
 1 3 2
 2 7 6
 3 5 8
 4 3 10
 5 2 3
 5 7 5
 
 4 5
 1 2 3
 1 3 5
 2 4 6
 3 4 4
 3 2 3
 */