import java.util.*;

public class Maksimivirtaus {

    public int n;
    public int[][] verkko;
    public int[][] alussa;
    public int[] tila;
    public boolean loytyi;
    ArrayDeque<Integer> polku;

    public Maksimivirtaus(int n) {
        this.n = n;
        tila = new int[n + 1];
        polku = new ArrayDeque<>();
        loytyi = false;
        verkko = new int[n + 1][n + 1];
        alussa = new int[n + 1][n + 1];
    }

    public void lisaaKaari(int a, int b, int p) {
        verkko[a][b] += p;
        alussa[a][b] += p;
    }

    void syvyyshaku(int s) {
        if (tila[s] == 1) {
            return;
        }
        if (loytyi) {
            return;
        }
        polku.addLast(s);
        if (s == n) {
            System.out.println("polku löytyi :)");
            loytyi = true;
            return;
        }
        tila[s] = 1;
        for (int i = 1; i <= n; i++) {
            if (verkko[s][i] > 0) {
                syvyyshaku(i);
            }
        }
        if (loytyi) {
            return;
        }
        polku.removeLast();
    }

    public int laske() {
        int pienin = 999999999;
        int virtaus = 0;

        for (int a = 1;;) {

            syvyyshaku(a);
            if (loytyi) {
                System.out.println(polku);
                int edellinen = 0;
                for (Integer nykyinen : polku) {
                    if (edellinen != 0) {
                        pienin = Math.min(pienin, verkko[edellinen][nykyinen]);
                    }
                    edellinen = nykyinen;
                }
                System.out.println("Pienin: " + pienin);
                edellinen = 0;

                for (Integer nykyinen : polku) {
                    if (edellinen != 0) {
                        verkko[edellinen][nykyinen] -= pienin;
                        verkko[nykyinen][edellinen] += pienin;
                    }
                    edellinen = nykyinen;
                }
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        if (alussa[i][j] > 0 && alussa[i][j] != verkko[i][j]) {
                            System.out.println(i + " " + j + " " + (alussa[i][j] - verkko[i][j]));
                        }
                    }
                }
            }

            virtaus += pienin;

            return virtaus;
        }
    }
}