#include <cstdio>
#include <cstring>

#pragma warning(disable : 4996)

using namespace std;

// O(M * N * log2(MaxCapacity))
#define MaxN 1000
#define MaxM 5000
#define MaxLog 16 // [log2(MaxCapacity)]
#define NIL -1

struct Network {
    struct Edge {
        int v, cap;
        int next;
    } G[2 * MaxM];

    int head[MaxN];
    int N;
    int edgePtr;

    void SetSize(const int numNodes) {
        memset(head, NIL, 4 * numNodes);
        N = numNodes;
        edgePtr = 0;
    }

    void AddEdge(const int u, const int v, const int cap) {
        G[edgePtr].v = v;
        G[edgePtr].cap = cap;
        G[edgePtr].next = head[u];
        head[u] = edgePtr++;
    }

    int dist[MaxN];
    int Q[MaxN];

    bool BFS(const int step) {
        int qHead = 0, qTail = 1;
        memset(dist, 0, 4 * N);
        Q[0] = 0;
        dist[0] = 1;
        while ((qHead != qTail) && (!dist[N - 1])) {
            const int node = Q[qHead++];
            for (int i = head[node]; i != NIL; i = G[i].next) {
                const int son = G[i].v;
                if (G[i].cap >= step && !dist[son]) {
                    dist[son] = dist[node] + 1;
                    Q[qTail++] = son;
                }
            }
        }
        return dist[N - 1];
    }
    
    int to[MaxN];

    bool DFS(const int node, const int step) {
        if (node == N - 1) {
            return true;
        }
        for (; to[node] != NIL; to[node] = G[to[node]].next) {
            if ((G[to[node]].cap >= step) && (dist[G[to[node]].v] == dist[node] + 1)
                && DFS(G[to[node]].v, step)) {
                G[to[node]].cap -= step;
                G[to[node] ^ 1].cap += step;
                return true;
            }
        }
        return false;
    }

    int ScalingFlow() {
        int flow = 0;
        int step = (1 << MaxLog);
        while (step) {
            if (BFS(step)) {
                memmove(to, head, 4 * N);
                while (DFS(0, step)) {
                    flow += step;
                }
            } else {
                step >>= 1;
            }
        }
        return flow;
    }

} Dinic;

int main() {
    freopen("maxflow.in", "rb", stdin);
    freopen("maxflow.out", "wb", stdout);
    
    int N, M;
    scanf("%d %d", &N, &M);
    Dinic.SetSize(N);
    for (int i = 0; i < M; i++) {
        int u, v, cap;
        scanf("%d %d %d", &u, &v, &cap);
        Dinic.AddEdge(u - 1, v - 1, cap);
        Dinic.AddEdge(v - 1, u - 1, 0);
    }
    printf("%d\n", Dinic.ScalingFlow());
    return 0;
}