#include<fstream>
#include<vector>
#define NMAX 1010

using namespace std;

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

vector<int> a[NMAX];
int n, m, vz[NMAX], t[NMAX], coada[NMAX], c[NMAX][NMAX], f[NMAX][NMAX];

void Citeste()
{
    int x, y, i;

    fin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        fin>>x>>y;
        fin>>c[x][y];
        a[x].push_back(y);
        a[y].push_back(x);
    }
}

bool bfs(int s)
{
    int p=1, u=1, nod, i;
    vector<int> :: iterator it;

    for (i=1; i<=n; ++i) vz[i]=t[i]=0;

    coada[1]=1; vz[1]=1; t[1]=-1;
    while (p<=u)
    {
        nod=coada[p++];

        for (it=a[nod].begin(); it!=a[nod].end(); ++it)
            if (!vz[*it] && c[nod][*it]-f[nod][*it]>0)
            {
                coada[++u]=*it;
                vz[*it]=1; t[*it]=nod;
            }
    }

    if (u>1) return 1;
    return 0;
}

int Minim(int nod)
{
    if (t[nod]!=-1)
     return min(c[t[nod]][nod]-f[t[nod]][nod], Minim(t[nod]));
    return NMAX*NMAX;
}

void Satureaza(int nod, int mn)
{
    if (t[nod]!=-1)
    {
        f[t[nod]][nod]+=mn;
        f[nod][t[nod]]-=mn;
        Satureaza(t[nod], mn);
    }
}

void Solve()
{
    int i, mn;

    while (bfs(1))
    {
        for (i=2; i<n; ++i)
            if (vz[i] && c[i][n])
            {
                mn=min(c[i][n]-f[i][n], Minim(i));
                if (mn)
                {
                    f[i][n]+=mn; f[n][i]-=mn;
                    Satureaza(i, mn);
                }
            }
    }

    int sum=0;
    for (i=1; i<n; ++i)
        sum+=f[i][n];
    g<<sum<<"\n";
}

int main()
{
    Citeste();

    Solve();

    fin.close();
    g.close();
    return 0;
}