/// Maximum Flow algorithm
/// The numbering of the vertices begins from 1 i.e. 1 is always the source
/// The target(sink) is the last vertex i.e. if number of vertices is "v", then "v" is always the target(sink)
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>

#include <fstream> ///infoarena.ro wants the output in a file...

using namespace std;

const int maxn = 1005;
vector<int> adj[maxn]; /// "adj[x] = {y1, y2, ..., yn}" means that vertices y1, y2, ..., yn are adjacent to x

map <pair<int, int>, int> flow; /// "map[(x,y)] = n" means the current flow from x to y is n

vector < vector<int> > path; /// stores every path from the source to the target(sink)
queue < vector<int> > bfs; /// used for calculating "path"

int maxFlow;

int main(){

/// 1) cin the information

    int v, e; /// v - number of vertexes(vertices), e - number of edges
    cin >> v >> e;

    for(int i=0; i<e; i++){
        int x, y, capacity;
        cin >> x >> y >> capacity;

        flow[{x,y}] = capacity; /// in the beginning we say so, because this is how the algorithm works
        flow[{y,x}] = 0;        /// -||-

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

/// 2) construct the queue "path" i.e. find all possible paths

    vector<int> vect = {1}; /// 1 is the source
    bfs.push(vect);

    while(!bfs.empty()){
        vector<int> currVect = bfs.front();
        int lastVert = currVect[currVect.size()-1];
        bfs.pop();

        if(lastVert == v){ /// "v" is the target(sink), so the path is complete
            path.push_back(currVect);
        }
        else{ /// the path is not complete
            for(int i=0; i<adj[lastVert].size(); i++){
                int currNeighbour = adj[lastVert][i];

                if( find(currVect.begin(), currVect.end(), currNeighbour) - currVect.begin() == currVect.size() ){ /// i.e. currNeighbour is not used
                    vector<int> note = currVect;
                    note.push_back(currNeighbour);
                    bfs.push(note);
                }
            }
        }
    }

/// 3) begin editing the map "flow" by the algorithm which is described in my notebook... XD it is too long for me to write it here

    for(int i = 0; i<path.size(); i++){

        int minFlow = 2*1e9;
        for(int j=0; j<path[i].size()-1; j++){
            minFlow = min(minFlow, flow[{path[i][j],path[i][j+1]}]);
        }

        for(int j=0; j<path[i].size()-1; j++){
            flow[{path[i][j],path[i][j+1]}] -= minFlow;
            flow[{path[i][j+1],path[i][j]}] += minFlow;
        }

        maxFlow += minFlow;
    }

    ofstream myfile;
    myfile.open ("maxflow.out");
    myfile << maxFlow;
    myfile.close();

    return 0;
}
/*
Example:

In:
4 5
1 2 3
1 3 5
2 4 6
3 4 4
3 2 3

Out:
8
*/