#include <stdio.h>
#include <vector>
#include <queue>

#define MAXN 1001
#define MAXM 5001

using namespace std;

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

inline void readAndBuild() {
    scanf("%d%d", &V, &E);
    s = 1;
    t = V;
    
    int x, y, z;
    for (int e = 0; e < E; ++ e) {
        scanf("%d%d%d", &x, &y, &z);
        
        V ++;
        
        Gf[x].push_back(V);
        cf[x][V] = z;
        Gf[V].push_back(y);
        cf[V][y] = z;
        
        Gf[y].push_back(V);
        Gf[V].push_back(x);
    }
}

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

inline int maxFlowEdmondsKarp() {
    int maxFlow = 0;
    
    for (bool isPath = bfs(); isPath; isPath = bfs()) {
        int cfpath = 0;
        if (cf[father[t]][t] != 0) {
            cfpath = cf[father[t]][t] - f1[father[t]][t];
        } else {
            cfpath = f1[t][father[t]];
        }
        
        for (int node = father[t]; node != s; node = father[node]) {
            int fedge = 0;
            if (cf[father[node]][node] != 0) {
                fedge = cf[father[node]][node] - f1[father[node]][node];
            } else {
                fedge = f1[node][father[node]];
            }
            
            if (fedge < cfpath) cfpath = fedge;
        }
        
        maxFlow += cfpath;
        
        for (int node = t; node != s; node = father[node]) {
            f1[father[node]][node] += cfpath;
            f1[node][father[node]] += cfpath;
        }
    }
    
    return maxFlow;
}

int main() {
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    
    readAndBuild();
    int F = maxFlowEdmondsKarp();
    printf("%d\n", F);
    
    return 0;
}