import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class TestGen {
    PrintWriter out;
    int tNumber = 0;
    Random random = new Random(1);

    static class Edge {
        int a, b;
        int cost;

        Edge(int a, int b, int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }
    }

    static class Test {
        int n, k;
        ArrayList<Edge> edges = new ArrayList<Edge>();
        int[] p, r;

        Test(int n, int k) {
            this.n = n;
            this.k = k;
            p = new int[n];
            r = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
        }

        int get(int x) {
            if (p[x] == x) {
                return p[x];
            }
            return p[x] = get(p[x]);
        }

        void union(int a, int b) {
            a = get(a);
            b = get(b);
            if (a == b) {
                return;
            }
            if (r[a] > r[b]) {
                p[b] = a;
            } else if (r[a] < r[b]) {
                p[a] = b;
            } else {
                p[a] = b;
                r[b]++;
            }
        }

        void addEdge(int a, int b, int cost) {
            edges.add(new Edge(a, b, cost));
            union(a, b);
        }

        void check() {
            if (k < 1 || k > n - 1) {
                throw new AssertionError();
            }
            for (int i = 0; i < n; i++) {
                if (get(p[i]) != get(p[0])) {
                    throw new AssertionError("" + i);
                }
            }
        }
    }

    public void write(Test t) throws IOException {
        t.check();
        out = new PrintWriter(String.format("%02d", ++tNumber));
        out.println(t.n + " " + t.edges.size() + " " + t.k);
        Collections.shuffle(t.edges, random);
        for (Edge e : t.edges) {
            out.println((e.a + 1) + " " + (e.b + 1) + " " + e.cost);
        }
        out.close();
    }


    Test makeRandom(int n, int m) {
        return makeRandom(n, m, random.nextInt(n - 1) + 1);
    }


    Test makeRandom(int n, int m, int k) {
        int zeroes = random.nextInt(m - n + 1);
        return makeRandom(n, m, k, zeroes);
    }

    Test makeRandom(int n, int m, int k, int zeroes) {
        Test test = makeTree(n, k);
        int ones = m - n - 1 - zeroes;
        if (ones < 0) {
            throw new AssertionError("Ones = " + ones);
        }
        if (zeroes < 0) {
            throw new AssertionError("Zeroes = " + zeroes);
        }
        test = addRandomOneEdges(test, ones);
        test = addRandomZeroEdges(test, zeroes);
        return test;
    }


    Test makeSpecial1(int n, int m, int k, int realk) {
        Test test = new Test(n, random.nextInt(n - 1));
        for (int i = 0; i < realk; i++) {
            int a, b;
            do {
                a = random.nextInt(n);
                b = random.nextInt(n);
            } while (test.get(a) == test.get(b));
            test.addEdge(a, b, 1);
        }
        for (int i = 0; i < m - realk; i++) {
            int a, b;
            do {
                a = random.nextInt(n);
                b = random.nextInt(n);
            } while (a == b);
            test.addEdge(a, b, 0);
        }
        return test;
    }

    Test makeTree(int n, int k) {
        Test test = new Test(n, k);
        ArrayList<Integer> costs = new ArrayList<Integer>();
        for (int i = 0; i < k; i++) {
            costs.add(1);
        }
        for (int i = 0; i < n - 1 - k; i++) {
            costs.add(0);
        }
        Collections.shuffle(costs, random);
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            do {
                a = random.nextInt(n);
                b = random.nextInt(n);
            } while (test.get(a) == test.get(b));
            test.addEdge(a, b, costs.get(i));
        }
        return test;
    }

    Test addRandomZeroEdges(Test test, int m) {
        for (int i = 0; i < m; i++) {
            int a, b;
            do {
                a = random.nextInt(test.n);
                b = random.nextInt(test.n);
            } while (a == b);
            test.addEdge(a, b, 0);
        }
        return test;
    }

    Test addRandomOneEdges(Test test, int m) {
        for (int i = 0; i < m; i++) {
            int a, b;
            do {
                a = random.nextInt(test.n);
                b = random.nextInt(test.n);
            } while (a == b);
            test.addEdge(a, b, 1);
        }
        return test;
    }

    Test incK(Test t, int delta) {
        t.k += delta;
        return t;
    }

    Test setK(Test t, int k) {
        t.k = k;
        return t;
    }

    Test makeSpecial1(int n, int m) {
        Test test = new Test(n, n - 1);
        for (int i = 0; i < m / 3 - 10; i++) {
            int a, b;
            do {
                a = random.nextInt(test.n / 2);
                b = random.nextInt(test.n / 2);
            } while (a == b);
            test.addEdge(a, b, 1);
        }
        for (int i = 0; i < m / 3 - 10; i++) {
            int a, b;
            do {
                a = random.nextInt(test.n / 2) + test.n / 2;
                b = random.nextInt(test.n / 2) + test.n / 2;
            } while (a == b);
            test.addEdge(a, b, 0);
        }
        for (int i = 0; i < 10; i++) {
            int a, b;
            do {
                a = random.nextInt(test.n / 2);
                b = random.nextInt(test.n / 2) + test.n / 2;
            } while (a == b);
            test.addEdge(a, b, random.nextInt(2));
        }
        for (int i = 0; i < n; i++) {
            if (test.get(i) != test.get(0)) {
                test.addEdge(i, 0, 0);
            }
        }
        return test;
    }

    final int PART_N = 700;
    final int PART_M = 1000;

    final int MAX_N = 100000;
    final int MAX_M = 200000;


    public void run() throws IOException {

        write(makeTree(PART_N, random.nextInt(PART_N - 1) + 1));
        write(makeRandom(PART_N, PART_M, random.nextInt(PART_N - 1) + 1, 0));
        write(makeRandom(PART_N, PART_M, random.nextInt(PART_N - 1) + 1, PART_M - PART_N - 1));
        write(incK(makeRandom(PART_N, PART_M, random.nextInt(PART_N - 10) + 1), 5));
        for (int i = 0; i < 5; i++) {
            write(makeRandom(PART_N / 2, PART_M));
        }
        write(makeRandom(999, PART_M));


        write(makeTree(MAX_N, random.nextInt(MAX_N - 1) + 1));
        write(makeRandom(MAX_N, MAX_M, random.nextInt(MAX_N - 1) + 1, 0));
        write(makeRandom(MAX_N, MAX_M, random.nextInt(MAX_N - 1) + 1, MAX_M - MAX_N - 1));
        write(makeRandom(MAX_N, MAX_M, 1, MAX_M - MAX_N - 1));
        write(makeRandom(MAX_N, MAX_M, 1, MAX_M - MAX_N - 10));
        write(makeRandom(MAX_N, MAX_M, MAX_N - 1, MAX_M - MAX_N - 1));
        write(incK(makeRandom(MAX_N, MAX_M, random.nextInt(MAX_N - 10) + 1), 5));
        for (int i = 0; i < 5; i++) {
            write(makeRandom(MAX_N, MAX_M));
        }
        write(makeSpecial1(MAX_N, MAX_M));
        write(setK(addRandomZeroEdges(makeTree(MAX_N, 0), MAX_M - MAX_N), MAX_N - 1));
        write(setK(addRandomOneEdges(makeTree(MAX_N, MAX_N - 1), MAX_M - MAX_N), 1));

    }

    public static void main(String[] args) throws IOException {
        new TestGen().run();
    }
}