#include <fstream>
#include <vector>
#include <queue>

#define MAXN 1001

using namespace std;

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

int V, E;
vector <int> Gf[MAXN];
int c[MAXN][MAXN];
int s, t;
int father[MAXN];
int f1[MAXN][MAXN];

inline void readAndBuild() {
    in >> V >> E;
    s = 1;
    t = V;
    
    int x, y, z;
    for (int e = 0; e < E; ++ e) {
        in >> x >> y >> z;
        
        if (c[y][x] == 0) {
            Gf[x].push_back(y);
            Gf[y].push_back(x);
        }
        
        c[x][y] = z;
    }
}

inline bool bfs() {
    bool sinkReached = false;
    
    queue <int> q;
    q.push(s);
    
    for (int i = 1; i <= V; ++ i) {
        father[i] = -1;
    }
    father[s] = 0;
    
    for (int node = q.front(); !q.empty(); node = q.front()) {
        q.pop();
        
        // let the bfs finish
        if (node == t) {
            sinkReached = true;
        }
        
        for (vector <int>::iterator it = Gf[node].begin(); it != Gf[node].end(); ++ it) {
            if (father[*it] == -1 && f1[node][*it] < c[node][*it]) {
                father[*it] = node;
                q.push(*it);
            }
        }
    }
    
    return sinkReached;
}

inline int maxFlowDinicVariation() {
    int maxFlow = 0;
    
    for (int sinkReached = bfs(); sinkReached; sinkReached = bfs()) {
        for (vector <int>::iterator it = Gf[t].begin(); it != Gf[t].end(); ++ it) {
            if (f1[*it][t] < c[*it][t] && father[*it] != -1) {
                int cfpath = c[*it][t] - f1[*it][t];
                for (int node = *it; node != s; node = father[node]) {
                    if (cfpath > c[father[node]][node] - f1[father[node]][node]) {
                        cfpath = c[father[node]][node] - f1[father[node]][node];
                    }
                }
                
                maxFlow += cfpath;
                
                father[t] = *it;
                for (int node = t; node != s; node = father[node]) {
                    f1[father[node]][node] += cfpath;
                    f1[node][father[node]] -= cfpath;
                }
            }
        }
    }
    
    return maxFlow;
}

int main() {
    readAndBuild();
    int F = maxFlowDinicVariation();
    out << F << '\n';
    
    return 0;
}