/**
 * Задача "Игра Bloxx City"
 * 4-я Интернет-олимпиада сезона 2009-2010, усложненный уровень.
 * Автор задачи: Владимир Ульянцев, ulyantsev@rain.ifmo.ru
 * Автор решения: Максим Буздалов, buzdalov@rain.ifmo.ru
 *
 */

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

public class bloxx_mb {
    private static void myAssert(String msg, boolean exp) {
        if (!exp) {
            throw new AssertionError(msg);
        }
    }

    static class Profile {
        final int[] vals;
        final int sum;
        final Profile back;

        Profile(int[] vals, int sum, Profile back) {
            this.vals = vals;
            this.sum = sum;
            this.back = back;
        }

        public int hashCode() {
            return Arrays.hashCode(vals);
        }

        public boolean equals(Object o) {
            return Arrays.equals(vals, ((Profile) (o)).vals);
        }
    }

    static boolean isValid(int mid, int n, int s, int e, int w) {
        int mask = 1 | (1 << s) | (1 << n) | (1 << e) | (1 << w);
        int mmask = (1 << mid) - 1;
        return (mask & mmask) == mmask;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader("bloxx.in"));
        int rows, cols;
        {
            StringTokenizer st = new StringTokenizer(in.readLine());
            rows = Integer.parseInt(st.nextToken());
            cols = Integer.parseInt(st.nextToken());
            myAssert("row count is out of bounds", 1 <= rows && rows <= 10);
            myAssert("column count is out of bounds", 1 <= cols && cols <= 10);
            myAssert("square is out of bounds", rows * cols <= 16);
        }

        int[][] pos = new int[rows][cols];
        for (int i = 0; i < rows; ++i) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int j = 0; j < cols; ++j) {
                int v = Integer.parseInt(st.nextToken());
                myAssert("intial height is out of bounds", 0 <= v && v <= 5);
                pos[i][j] = v;
            }
        }

        boolean swapped = false;
        if (rows > cols) {
            swapped = true;
            int[][] np = new int[cols][rows];
            for (int i = 0; i < cols; ++i) {
                for (int j = 0; j < rows; ++j) {
                    np[i][j] = pos[j][i];
                }
            }
            int tmp = rows;
            rows = cols;
            cols = tmp;
            pos = np;
        }

        Map<Profile, Profile> curr = new HashMap<Profile, Profile>();
        Profile initial = new Profile(new int[2 * rows], 0, null);
        curr.put(initial, initial);

        int[] vals0 = new int[] {0};
        int[] vals1 = new int[] {1, 2, 3, 4, 5};

        for (int col = 0; col <= cols; ++col) {
            for (int row = 0; row < rows; ++row) {
                Map<Profile, Profile> next = new HashMap<Profile, Profile>();
                for (Profile p : curr.values()) {
                    for (int v : col == cols ? vals0 : vals1) {
                        if (col < cols && pos[row][col] != 0 && pos[row][col] != v) {
                            continue;
                        }
                        int[] currVals = p.vals;
                        int vN = row == 0 ? 0 : currVals[row - 1];
                        int vS = row + 1 == rows ? 0 : currVals[rows + row + 1];
                        int vE = v;
                        int vW = currVals[row];
                        if (col > 0 && pos[row][col - 1] != 0 || isValid(currVals[rows + row], vN, vS, vE, vW)) {
                            int[] nextVals = currVals.clone();
                            nextVals[row] = currVals[rows + row];
                            nextVals[rows + row] = v;
                            Profile np = new Profile(nextVals, p.sum + v, p);
                            Profile at = next.get(np);
                            if (at == null || np.sum > at.sum) {
                                next.put(np, np);
                            }
                        }
                    }
                }
                curr = next;
            }
        }

        Profile max = null;
        for (Profile p : curr.values()) {
            if (max == null || max.sum < p.sum) {
                max = p;
            }
        }

        int res = max.sum;
        int[][] ans = new int[rows][cols];
        for (int col = cols; col >= 0; --col) {
            for (int row = rows - 1; row >= 0; --row) {
                if (col != cols) {
                    ans[row][col] = max.sum - max.back.sum;
                }
                max = max.back;
            }
        }

        PrintWriter out = new PrintWriter("bloxx.out");

        List<Integer> rs = new ArrayList<Integer>();
        List<Integer> cs = new ArrayList<Integer>();
        List<Integer> hs = new ArrayList<Integer>();
        for (int h = 1; h <= 5; ++h) {
            for (int row = 0; row < rows; ++row) {
                for (int col = 0; col < cols; ++col) {
                    if (ans[row][col] == h && pos[row][col] == 0) {
                        rs.add(row + 1);
                        cs.add(col + 1);
                        hs.add(h);
                    }
                }
            }
        }

        out.println(res);
        out.println(rs.size());
        for (int i = 0; i < rs.size(); ++i) {
            if (swapped) {
                out.println(cs.get(i) + " " + rs.get(i) + " " + hs.get(i));
            } else {
                out.println(rs.get(i) + " " + cs.get(i) + " " + hs.get(i));
            }
        }
        out.close();
    }
}
