#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int Nmax = 1010;
const int Mmax = 5010;

ifstream F("maxflow.in");
ofstream G("maxflow.out");

#define IT(type) vector<type>::iterator

int N,M,total_flow;
vector<int> V[Nmax];
vector<int> leafs;

int capacity[Nmax][Nmax];
int last[Nmax],Cmin[Nmax];

int find_paths(int source,int target)
{
    queue<int> Q;
    memset(last,0,sizeof(last));

    last[source] = -1;
    Q.push( source );

    while ( Q.size() )
    {
        int node = Q.front();
        Q.pop();

        for (IT(int) where=V[node].begin();where!=V[node].end();++where)
            if ( capacity[node][*where] > 0 && last[*where] == 0 )
            {
                last[*where] = node;
                Q.push( *where );
            }
    }

    leafs.clear();
    int not_leaf[Nmax];
    memset(not_leaf,0,sizeof(not_leaf));

    for (int i=1;i<=N;++i)
        if ( i != target && i != source )
            not_leaf[ last[i] ] = 1;
    for (IT(int) node=V[target].begin();node!=V[target].end();++node)
        if ( not_leaf[ *node ] == 0 )
            leafs.push_back( *node );

    if ( last[target] != 0 )
        return 1;
    return 0;
}

int main()
{
    F>>N>>M;
    for (int i=1,x,y,c;i<=M;++i)
    {
        F>>x>>y>>c;
        if ( capacity[x][y] == 0 && capacity[y][x] == 0 )
        {
            V[ x ].push_back( y );
            V[ y ].push_back( x );
        }
        capacity[x][y] += c;
    }

    int source = 1;
    int target = N;

    while ( find_paths(source,target) != 0 )
    {
        for (IT(int) leaf=leafs.begin();leaf!=leafs.end();++leaf)
        {
            Cmin[*leaf] = capacity[*leaf][target];
            for (int now=*leaf;now!=source;now=last[now])
                Cmin[*leaf] = min( Cmin[*leaf] , capacity[last[now]][now] );
            total_flow += Cmin[*leaf];

            for (int now=*leaf;now!=source;now=last[now])
            {
                capacity[last[now]][now] -= Cmin[*leaf];
                capacity[now][last[now]] += Cmin[*leaf];
            }
            capacity[*leaf][target] -= Cmin[*leaf];
        }
    }

    G<<total_flow<<'\n';
}