// Exemplo de implementacao de algoritmo de Edmonds-Karp
// usando lista de adjacencias + matriz de capacidades
// (implementacao com vector)

import java.util.*;

// Classe para no da fila do BFS: pares (no, capacidade)
class NodeQ {
    public int node;
    public int flow;

    NodeQ(int n, int f) {
        node = n;
        flow = f;
    }
}

// Classe que representa um grafo
class Graph {
    int n;                       // Numero de nos do grafo
    Vector<Vector<Integer>> adj; // Lista de adjacencias
    int cap[][];                 // Matriz de capacidades

    Graph(int n) {
        this.n = n;
        adj = new Vector<>();
        for (int i=0; i<=n; i++) adj.add(new Vector<Integer>());
        cap = new int[n+1][n+1]; // +1 se os nos comecam em 1 ao inves de 0
    }
  
    void addLink(int a, int b, int c) {
        // adjacencias do grafo nao dirigido, porque podemos ter de andar no sentido
        // contrario ao procurarmos caminhos de aumento
        adj.get(a).add(b);
        adj.get(b).add(a);
        cap[a][b] = c;
    }
    
    // BFS para encontrar caminho de aumento
    // devolve valor do fluxo nesse caminho
    int bfs(int s, int t, int[] parent) {
        for (int i=1; i<=n; i++) parent[i] = -1;

        parent[s] = -2;         
        Queue<NodeQ> q = new LinkedList<>(); // fila do BFS
        // inicializar com no origem e capacidade infinita
        q.add(new NodeQ(s, Integer.MAX_VALUE));

        while (!q.isEmpty()) {
            // returar primeiro no da fila
            int cur = q.peek().node;
            int flow = q.peek().flow;
            q.poll();

            // percorrer nos adjacentes ao no atual (cur)
            for (int next : adj.get(cur)) {
                // se o vizinho ainda nao foi visitado (parent==-1)
                // e a aresta respetiva ainda tem capacidade para passar fluxo
                if (parent[next] == -1 && cap[cur][next]>0) {
                    parent[next] = cur;                        // atualizar pai
                    int new_flow = Math.min(flow, cap[cur][next]); // atualizar fluxo
                    if (next == t) return new_flow;            // chegamos ao final?
                    q.add(new NodeQ(next, new_flow));          // adicionar a fila
                }
            }
        }
    
        return 0;
    }

    // Algoritmo de Edmonds-Karp para fluxo maximo entre s e t
    // devolve valor do fluxo maximo (cap[][] fica com grafo residual)
    int maxFlow(int s, int t) {
        int flow = 0;                // fluxo a calcular
        int[] parent = new int[n+1]; // array de pais (permite reconstruir caminho)
    
        while (true) {
            int new_flow = bfs(s, t, parent); // fluxo de um caminho de aumento
            if (new_flow == 0) break;         // se nao existir, terminar

            // imprimir fluxo e caminho de aumento
            System.out.print("Caminho de aumento: fluxo " + new_flow + " | " + t);
	    
            flow += new_flow;  // aumentar fluxo total com fluxo deste caminho
            int cur = t;
            while (cur != s) { // percorrer caminho de aumento e alterar arestas
                int prev = parent[cur];	
                cap[prev][cur] -= new_flow;
                cap[cur][prev] += new_flow;
                cur = prev;
                System.out.print(" <- " + cur); // imprimir proximo no do caminho
            }
            System.out.println();
        }
	
        return flow;
    }       
}


class edmondskarp {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        Graph g = new Graph(n);
        int e = in.nextInt();
        for (int i=0; i<e; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            g.addLink(a, b, c);
        }

        // Execucao exemplo usando 1 como no origem a 4 como o destino
        int flow = g.maxFlow(1, 4);
        System.out.println("Fluxo maximo: " + flow);
    }    
}