#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1005;
bool ver[NMAX];
int dist[NMAX][NMAX],flow[NMAX][NMAX];
int last[NMAX],n,m,cost;
vector <int> v[NMAX];
deque <int> q;

bool bfs()
{
    for(int i=1;i<=NMAX-5;i++)
        ver[i]=0;
    q.push_back(1);
    ver[1]=true;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop_front();
        for(int i=0;i<v[nod].size();i++)
        {
            int vecin=v[nod][i];
            if(ver[vecin]==0 and dist[nod][vecin]>flow[nod][vecin])
            {
                ver[vecin]=1;
                last[vecin]=nod;
                q.push_back(vecin);
            }
        }
    }
    if(ver[n]==true) return 1;
    return 0;
}

int main()
{
    fin >> n >> m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        fin >> x >> y >> cost;
        v[x].push_back(y);
        v[y].push_back(x);
        dist[x][y]=cost;
    }
    int rasp=0;
    while(bfs()==true)
    {
        for(int i=0;i<v[n].size();i++)
        {
            int x=v[n][i];
            if(ver[x]==true and dist[x][n]>flow[x][n])
            {
                int dif=dist[x][n]-flow[x][n];
                int aux=x;
                while(aux!=1)
                {
                    int lst=last[aux];
                    dif=min(dif,dist[lst][aux]-flow[lst][aux]);
                    aux=last[aux];
                }
                flow[x][n]+=dif;
                flow[n][x]-=dif;
                while(x!=1)
                {
                    int lst=last[x];
                    flow[lst][x]+=dif;
                    flow[x][lst]-=dif;
                    x=last[x];
                }
                rasp+=dif;
            }
        }
    }
    fout << rasp;
    return 0;
}