#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");
const int NMAX = 1005;
int N,M,c[NMAX][NMAX],f[NMAX][NMAX],viz[NMAX],pr[NMAX];
vector<int> v[NMAX];

void read()
{

    in>>N>>M;
    int x,y,cost;
    for(int i = 1;  i <= M ; ++i){

        in>>x>>y>>cost;
        v[x].push_back(y);
        v[y].push_back(x);
        c[x][y] += cost;
    }
}

void reset()
{

    for(int i = 1 ; i <= N ; ++i)
        viz[i] = 0;
}

int bfs()
{

    reset();
    queue<int> Q;
    Q.push(1);
    viz[1] = 1;
    while(!Q.empty()){
        int virf = Q.front();
        Q.pop();
        for(int i = 0 ; i < v[virf].size() ; ++i)
            if(!viz[v[virf][i]] && f[virf][v[virf][i]] != c[virf][v[virf][i]]){

                viz[v[virf][i]] = 1;
                pr[v[virf][i]] = virf;
                Q.push(v[virf][i]);
                if(v[virf][i] == N)
                    return 1;
            }
    }
    return 0;
}

int flux_maxim()
{

    int sol = 0,minim;
    for(; bfs() ; sol += minim){
        minim = 1 << 30;
        for(int act = N ; act != 1 ; act = pr[act])
            minim = min(minim,c[pr[act]][act] - f[pr[act]][act]);
        for(int act = N ; act != 1 ; act = pr[act]){
            f[pr[act]][act] += minim;
            f[act][pr[act]] -= minim;
        }
    }
    return sol;
}

int main()
{

    read();
    out<<flux_maxim();
    return 0;
}