#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);
            c[x][y] = z;
            
            Gf[y].push_back(x);
        } else {
            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();
        
        for (vector <int>::iterator it = Gf[node].begin(); it != Gf[node].end(); ++ it) {
            if (father[*it] == -1 && f1[node][*it] < c[node][*it]) {
                // do not push the sink on the queue
                // because we are interested only in paths that end at t
                // if we allow the construction of such paths
                // i.e. for some node x father[x] = t
                // and the path in the bfs looks like s ~> t -> x ~> y
                // (it is not an augmentation path)
                // we would end up with a cyclic path when we try to augment the flow
                // on path s ~> x -> t (x and t are adjacent)
                // this is due to the way we construct paths (see below)
                if (*it == t) {
                    sinkReached = true;
                } else {
                    father[*it] = node;
                    q.push(*it);
                }
            }
        }
    }
    
    return sinkReached;
}

// this is very similar to original Dinic
// however we do not augment all the paths
// on the level graph we obtain from bfs
// actually the augmentation paths may have different lengths
// some nodes may have multiple potential fathers
// and this is why we may miss some blocking flows
// in this case we only deal with the multiple fathers of the sink
// this results in good performance in practice
inline int maxFlowDinicVariation() {
    int maxFlow = 0;
    
    for (int sinkReached = bfs(); sinkReached; sinkReached = bfs()) {
        // attempt to augment all the paths of the form s ~> x -> t,
        // where there is an edge (x, t) in Ef
        // (implementation) because Gf is undirected graph,
        // we can find the parents of t in Gf[t]
        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];
                    }
                }
                
                // because we augment paths that share some edges
                // we could end up with 0 as the residual capacity of some path
                // notice that cfpath is never negative
                // (what we want is to have minimum cases of cfpath = 0)
                if (cfpath == 0) continue;
                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;
}