#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin ("maxflow.in");
ofstream fout ("maxflow.out");

struct vecini
{
    int e1;
    int cap;
};

vector <vecini> L[1013], L1[1013];
vector < pair<int,int> > D;
int n, m, a[1010][1010], b[1010][1010], T[1010], viz[1010], r[1010];
int abs(int x)
{
    return x>0?x:-x;
}
void citire()
{
    fin >> n >> m;
    int x, y, z;
    while(m--)
    {
        fin >> x >> y >> z;
        L[x].push_back({y, z});
        L1[y].push_back({x, z});
        a[x][y]=z;
        b[x][y]=0;
    }
}

bool BFS()
{
    int nod;
    queue <int> q;
    q.push(1);
    fill(viz,viz+n+1,0);
    fill(r,r+n+1,0);
    viz[1]=1;
    while(!q.empty())
    {
        nod=q.front();
        //cout << nod << endl;
        if(nod==n)
            return true;
        q.pop();
        for(unsigned int i=0;i<L[nod].size();i++)
        {
            int vecin=L[nod][i].e1;
            if (a[nod][vecin]-b[nod][vecin]>0 && !viz[vecin])
            {
                q.push(vecin);
                viz[vecin]=1;
                T[vecin]=nod;
                r[vecin]=a[nod][vecin]-b[nod][vecin];
            }

        }
        for(unsigned int i=0;i<L1[nod].size();i++)
        {
            int vecin=L1[nod][i].e1;
            if(b[nod][vecin]>0 && !viz[vecin])
            {
                q.push(vecin);
                viz[vecin]=1;
                T[vecin]=nod;
                r[vecin]=-b[nod][vecin];
            }
        }
    }
    return false;
}

void drum()
{
    pair <int, int> p;
    D.clear();
    int i=n;
    while(T[i]!=0)
    {
        p.first=T[i];
        p.second=i;
        D.push_back(p);
        i=T[i];
    }
}

int valrez()
{
    int mini=0xfffffff;
    for(unsigned int i=0;i<D.size();i++)
    {
        mini = min(mini,abs(r[D[i].second]));
    }
    return mini;
}

void crestere(int eps)
{
    int x, y;
    for(unsigned int i=0;i<D.size();i++)
        {
            x=D[i].first;
            y=D[i].second;
            if(r[y]>0)
            {
                b[x][y]+=eps;
            }
            else
            {
                b[y][x]-=eps;
            }
        }
}

int main()
{
    citire();
    while(BFS())
    {
        drum();
        /*cout << endl;
        for(int j=1;j<=n;j++)
            cout << j<<'-'<<r[j] << " ";
        cout << endl;
        for(unsigned int i=0;i<D.size();i++)
        {
            cout << D[i].first << " " << D[i].second <<' ' <<r[D[i].second]<< endl;
        }*/
        int eps= valrez();
        crestere(eps);
        //system("PAUSE");
    }
    int fluxmax=0;
    for(unsigned int i=0;i<L[1].size();i++)
    {
        fluxmax+=b[1][L[1][i].e1];
    }
    fout << fluxmax;
    return 0;
}