#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <iostream>
#define site vector<int>::iterator
#define DIM 1005
#define INF 0x3f3f3f3f

using namespace std;

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

int N,M;
vector <int> L[DIM];
bitset <DIM> viz;

int F[DIM][DIM],C[DIM][DIM],T[DIM],Cost,Flux,minim,D;

int bfs(){

    viz.reset();
    viz[1]=1;
    queue <int> Q;
    Q.push(1);

    while(!Q.empty()){
        int node=Q.front();
        Q.pop();
        for(site it=L[node].begin();it!=L[node].end();it++)
            if(!viz[*it] && C[node][*it] > F[node][*it]){
                viz[*it]=1;
                T[*it]=node;
                Q.push(*it);
            }
    }

    return viz[N];

}

int main(){

    fin >> N >> M;

    while(M--){
        int x,y,z;
        fin >> x >> y >> z;
        L[x].push_back(y);
        L[y].push_back(x);
        C[x][y]=z;
    }

    while(bfs()){
        for(site it=L[N].begin();it!=L[N].end();it++)
            if(F[*it][N] < C[*it][N] && viz[*it]){
                minim = C[*it][N] - F[*it][N];

                for(D=*it;T[D]!=0;D=T[D])
                    minim = min(C[T[D]][D]-F[T[D]][D],minim);

                Cost += minim;

                F[T[N]][N] += minim;
                F[N][T[N]] -= minim;

                for(D=*it;T[D]!=0;D=T[D])
                    F[T[D]][D] += minim,
                    F[D][T[D]] -= minim;

            }
    }

    fout << Cost << "\n";


}