#include <stdio.h>

int min(int x, int y)
{
    return x <= y ? x : y;
}

struct Flow
{
    // the max. no. of edges and nodes
    static const int EDGE_COUNT = 5000;
    static const int NODE_COUNT = 1000;

    // no node / no edge
    static const int NONE = -1;

    // infinity
    static const int INF = 0x3f3f3f3f;

    // the edges of the graph
    struct
    {
        int v;
        int capacity;
        int next;
    } edges[2 * EDGE_COUNT];

    // the first edge of each node
    int begin[NODE_COUNT];

    // the no. of nodes and no. of edges
    int n, m;

    // the source and the sink
    int source, sink;

    // inits the graph with _n nodes and the given source and sink
    void init(int _n, int _source, int _sink)
    {
        n = _n;
        m = 0;
        source = _source;
        sink = _sink;
        for(int i = 0; i < n; i++)
            begin[i] = NONE;
    }

    // adds an edge from u to v with the given capacity
    void add_edge(int u, int v, int capacity)
    {
        edges[m] = { v, capacity, begin[u] };
        begin[u] = m++;

        edges[m] = { u, 0, begin[v] };
        begin[v] = m++;
    }
};

// performs Edmonds-Karp algorithm on a graph
struct EdmondsKarp : public Flow
{
    // for each node, the edge to its parent in the BFS tree
    int to_parent[NODE_COUNT];

    // BFS to find augmenting paths
    bool bfs()
    {
        static int queue[NODE_COUNT];

        // init the parent edges
        for(int i = 0; i < n; i++)
            to_parent[i] = NONE;
        to_parent[source] = INF;

        // init the queue
        int qfront = 0, qtop = 0;
        queue[qtop++] = source;

        // while the queue isn't empty and no path was found, propagate
        while(qfront < qtop && to_parent[sink] == NONE)
        {
            int u = queue[qfront++];
            for(int i = begin[u]; i != NONE; i = edges[i].next)
            {
                int v = edges[i].v;
                if(edges[i].capacity != 0 && to_parent[v] == NONE)
                {
                    queue[qtop++] = v;
                    to_parent[v] = (i ^ 1);
                }
            }
        }

        // return whether or not a path was found
        return to_parent[sink] != NONE;
    }

    // augment the path according to the BFS tree found
    int augment()
    {
        int flow = INF;
        int v = sink;

        // move back and calculate the flow
        while(v != source)
        {
            int i = to_parent[v];
            flow = min(flow, edges[i ^ 1].capacity);
            v = edges[i].v;
        }

        if(flow == 0)
            return flow;

        // apply the flow
        v = sink;
        while(v != source)
        {
            int i = to_parent[v];
            edges[i].capacity += flow;
            edges[i ^ 1].capacity -= flow;
            v = edges[i].v;
        }

        return flow;
    }

    // finds the max flow in the graph
    int max_flow()
    {
        int flow = 0;

        // while there are augmenting paths found
        while(bfs())
        {
            for(int i = begin[sink]; i != NONE; i = edges[i].next)
                if(edges[i ^ 1].capacity != 0 && to_parent[edges[i].v] != NONE)
                {
                    to_parent[sink] = i;
                    flow += augment();
                }
        }

        return flow;
    }
};

struct Dinic : public Flow
{
    // the layer of each node in the layered network
    int layer[NODE_COUNT];

    // the last edge not filled in the last DFS push for each node
    int blocking_ptr[NODE_COUNT];

    // find a layered network
    bool layered_network()
    {
        // queue for BFS
        static int queue[NODE_COUNT];

        // reset the layers
        for(int i = 0; i < n; i++)
            layer[i] = NONE;
        layer[source] = 0;

        // init the queue
        int qfront = 0, qtop = 0;
        queue[qtop++] = source;

        // while there are nodes to visit
        while(qfront < qtop && layer[sink] == NONE)
        {
            int u = queue[qfront++];
            for(int i = begin[u]; i != NONE; i = edges[i].next)
            {
                int v = edges[i].v;
                if(edges[i].capacity != 0 && layer[v] == NONE)
                {
                    queue[qtop++] = v;
                    layer[v] = layer[u] + 1;
                }
            }
        }

        // return whether or not the sink was reached
        return layer[sink] != NONE;
    }

    // try to push some flow from u to the sink and return the quantity pushed
    int dfs(int u, int flow)
    {
        // if the sink is reached, push everything
        if(u == sink)
            return flow;

        // the flow pushed
        int max_flow = 0;

        // try to push through the children
        for(int& i = blocking_ptr[u]; i != NONE && flow > max_flow; i = edges[i].next)
        {
            int v = edges[i].v;
            if(edges[i].capacity != 0 && layer[v] == layer[u] + 1)
            {
                // push through edge i as much as possible
                int delta = dfs(v, min(flow - max_flow, edges[i].capacity));
                max_flow += delta;

                // update the capacities
                edges[i].capacity -= delta;
                edges[i ^ 1].capacity += delta;
            }
        }

        // return the flow pushed
        return max_flow;
    }

    // find a blocking flow
    int blocking_flow()
    {
        // reset the blocking pointers
        for(int i = 0; i < n; i++)
            blocking_ptr[i] = begin[i];

        // DFS from the source
        return dfs(source, INF);
    }

    // find the maximum flow
    int max_flow()
    {
        int flow = 0;

        // while there is a layered network
        while(layered_network())
            // find a blocking flow
            flow += blocking_flow();

        return flow;
    }
};

Dinic flow;

int main()
{
    // open the files
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);

    // read the graph
    int n, m;
    scanf("%d %d", &n, &m);
    flow.init(n, 0, n - 1);
    for(int i = 0; i < m; i++)
    {
        int u, v, capacity;
        scanf("%d %d %d", &u, &v, &capacity);
        u--; v--;

        flow.add_edge(u, v, capacity);
    }

    // calculate and print the flow
    printf("%d\n", flow.max_flow());
    return 0;
}