#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Graph {
    private:

        ifstream src;
        ofstream out;
        vector<vector<int> > G;
        vector<vector<int> > Flow;
        vector<vector<int> > Cap;
        vector<int> T;
        vector<int> U;
        vector<int> destSons;

        int getInt() {
            int x;
            src>>x;
            return x;
        }
        int n;

    public:
        int nodes() {
            return n;
        }

        void add(int x, int y, int c) {
            ////cout<<"addind edge from node "<<x<<" to node "<<y<<" of capacity "<<c;cin.get();
            G[x].push_back(y);
            if(y==n-1) destSons.push_back(x);
            //G[y].push_back(x);
            Cap[x][y] = c;// Cap[y][x] = c;
        }

        void load(char* c) {
            int m;
            src.open(c);
            src>>n>>m;
            //cout<<"Loading graph...\nn = "<<n<<"\nm = "<<m<<'\n';cin.get();
            G = vector<vector<int> >(n);
            Flow.assign(n,vector<int>(n,0));
            Cap.assign(n,vector<int>(n,0));
            U = vector<int> (n,0);
            T = vector<int> (n,0);
            //cout<<"Initialized components...\nAdding edges...";cin.get();
            while(m--) {
                //TODO : solve this damned thing!!!
                int x=getInt(),y=getInt(),c=getInt();
                add(x-1,y-1,c);
                //add(getInt()-1, getInt()-1, getInt());
            }
            //cout<<"Edges added.\nComputing maxFlow...";cin.get();
        }

        bool Bfs(int src, int dest) {
            fill(U.begin(),U.end(),0);
            //cout<<U.size();cin.get();
            queue<int> Q;
            Q.push(src);
            U[src]=1;
            while(!Q.empty()) {
                //cout<<">>>>>>>>>>>>>>Current node: "<<Q.front();cin.get();
                for(vector<int>::iterator it=G[Q.front()].begin(); it!=G[Q.front()].end(); it++) {
                    //cout<<"current son: "<<*it;cin.get();
                    //cout<<U[*it]<<" "<<Cap[Q.front()][*it]<<" "<<Flow[Q.front()][*it];cin.get();
                    if( !U[*it] && Cap[Q.front()][*it]>Flow[Q.front()][*it]) {
                        U[*it] = 1;
                        T[*it] = Q.front();
                        if(*it != dest) {
                            //cout<<"! pushed";cin.get();
                            Q.push(*it);
                        } else {
                            //cout<<"x it is the destination node";
                            cin.get();
                        }
                    }
                    else {
                        //cout<<"x no way";
                        cin.get();
                    }
                }
                Q.pop();
            }
            return U[dest];
        }

        int Dinic(int src, int dest) {
            int flow,r;
            for(flow=0; Bfs(src, dest); ) {
                for(vector<int>::iterator it=destSons.begin(); it!=destSons.end(); it++) {
                    if(U[*it] && Cap[*it][dest]>Flow[*it][dest]) {
                        r = Cap[*it][dest]-Flow[*it][dest];
                        for(int i=*it; i!=src && i; i=T[i])
                            r = min(r,Cap[T[i]][i]-Flow[T[i]][i]);
                        if (!r) break;
                        Flow[*it][dest]+=r;
                        Flow[dest][*it]-=r;
                        for(int i=*it; i!=src; i=T[i]) {
                            Flow[T[i]][i]+=r;
                            Flow[i][T[i]]-=r;
                        }
                        flow+=r;
                        //cout<<"on the chain of "<<*it<<" I got flow: "<<r;cin.get();
                    }
                }
                //cout<<"This time, I got flow: "<<flow;cin.get();
            }
            return flow;
        }

        void write(int x, char* c) {
            out.open(c);
            out<<x<<'\n';
            out.close();
        }
};

int main() {
    Graph G;
    G.load("maxflow.in");
    G.write(G.Dinic(0,G.nodes()-1), "maxflow.out");
    return 0;
}