import java.util.*;

public class Virtaus {
    static int n;
    static int[][] verkko;
    static int[][] alussa;
    
    static void lisaaKaari(int a, int b, int p) {
        verkko[a][b] += p;
        alussa[a][b] += p;
    }
    
    static int[] tila; // 0 = ei käyty, 1 = käyty
    static ArrayDeque<Integer> polku = new ArrayDeque<>();
    static boolean loytyi;
    
    static 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 static void main(String[] args) {
        //    5   2
        //   /->2->\ 12
        //  1       4->5
        //   \->3->/
        //    3  7
        n = 5;
        verkko = new int[n+1][n+1];
        alussa = new int[n+1][n+1];
        lisaaKaari(1,2,5);
        lisaaKaari(1,3,3);
        lisaaKaari(2,4,2);
        lisaaKaari(3,4,7);
        lisaaKaari(4,5,12);
        tila = new int[n+1];
        loytyi = false;
        syvyyshaku(1);
        if (loytyi) {
            System.out.println(polku);
            int pienin = 999999999;
            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]));
                    }
                }
            }
        }
    }
}