package fordFulkerson;

import java.io.*;
import java.util.*;

public class FordFulkerson {

    private static class Node {
        public int id;
        public List<Edge> edges;

        public Node(int id) {
            this.id = id;
            this.edges = new ArrayList<>();
        }
    }

    private static class Edge {
        public int fromId;
        public int toId;
        public int capacity;
        public int flow;
        public boolean backwards;
        public Edge counterpart;

        public Edge(int fromId, int toId, int capacity, int flow, boolean backwards) {
            this.fromId = fromId;
            this.toId = toId;
            this.capacity = capacity;
            this.flow = flow;
            this.backwards = backwards;
        }

        public void increaseFlow(int value) {
            flow += value;
            counterpart.flow -= value;
        }
    }

    private static class ResidualGraph {
        public List<Node> nodes;

        public int sourceId;
        public int sinkId;

        public ResidualGraph(int numNodes, int sourceId, int sinkId) {
            nodes = new ArrayList<>();
            this.sourceId = sourceId;
            this.sinkId = sinkId;

            for (int i = 0; i < numNodes; i++) {
                nodes.add(new Node(i));
            }
        }

        public void addEdge(int from, int to, int flow, int capacity) {
            Node fromNode = nodes.get(from);
            Node toNode = nodes.get(to);

            Edge forward = new Edge(from, to, capacity, flow, false);
            Edge backward = new Edge(to, from, capacity, capacity - flow, true);
            forward.counterpart = backward;
            backward.counterpart = forward;

            fromNode.edges.add(forward);
            toNode.edges.add(backward);
        }

        public int getTotalFlow() {
            int totalFlow = 0;
            for (Edge e : nodes.get(sourceId).edges) {
                totalFlow += e.flow;
            }
            return totalFlow;
        }

    }

    private static boolean findAugmentingPath(int currentNode, List<Edge> path, Set<Integer> visited, int sink, ResidualGraph graph) {
        if (currentNode == sink)
            return true;

        if (visited.contains(currentNode))
            return false;

        visited.add(currentNode);

        boolean found = false;

        for (Edge e : graph.nodes.get(currentNode).edges) {
            if (e.flow >= e.capacity) {
                continue;
            }

            path.add(e);
            found = findAugmentingPath(e.toId, path, visited, sink, graph);
            if (found) {
                break;
            }
            path.remove(e);
        }

        return found;
    }

    private static boolean augmentPath(ResidualGraph graph) {
        List<Edge> path = new ArrayList<>();
        boolean found = findAugmentingPath(graph.sourceId, path, new HashSet<>(), graph.sinkId, graph);

        if (!found)
            return false;

        int bottleneck = Integer.MAX_VALUE;

        for (Edge e : path) {
            bottleneck = Math.min(bottleneck, e.capacity - e.flow);
        }

        // update the edges
        for (Edge e : path) {
            e.increaseFlow(bottleneck);
        }

        return true;
    }

    private static void fordFulkerson(ResidualGraph graph) {
        while (true) {
            if (!augmentPath(graph))
                break;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner scn = new Scanner(new FileInputStream("maxflow.in"));
        int numNodes = scn.nextInt();
        int numEdges = scn.nextInt();

        ResidualGraph graph = new ResidualGraph(numNodes, 0, numNodes - 1);

        for (int i = 0; i < numEdges; i++) {
            int fromId = scn.nextInt() - 1;
            int toId = scn.nextInt() - 1;
            int capacity = scn.nextInt();
            graph.addEdge(fromId, toId, 0, capacity);
        }

        scn.close();

        fordFulkerson(graph);

        FileWriter writer = new FileWriter("maxflow.out");

        writer.write(String.valueOf(graph.getTotalFlow()));
        writer.flush();
        writer.close();

    }
}