import static java.util.Arrays.copyOf;

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

public class TestsGen {

	static int testNum = 1;

	static class DSU {
		int[] p;
		int[] r;

		public DSU(int n) {
			p = new int[n];
			r = new int[n];
			clear();
		}

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

		boolean union(int x, int y) {
			x = get(x);
			y = get(y);
			if (x == y) {
				return false;
			}
			if (r[x] >= r[y]) {
				if (r[x] == r[y]) {
					r[x]++;
				}
				p[y] = x;
			} else {
				p[x] = y;
			}
			return true;
		}

		void clear() {
			for (int i = 0; i < p.length; i++) {
				p[i] = i;
				r[i] = 0;
			}
		}
	}

	static class Edge {
		int from;
		int to;
		int w;

		public Edge(int from, int to, int w) {
			this.from = from;
			this.to = to;
			this.w = w;
		}

		@Override
		public int hashCode() {
			return from * 31 + to;
		}

		@Override
		public boolean equals(Object obj) {
			Edge other = (Edge) obj;
			if (from != other.from)
				return false;
			if (to != other.to)
				return false;
			return true;
		}

	}

	static class Test {
		Edge[] edges;
		int n;

		public Test(int n, Edge[] e) {
			this.n = n;
			this.edges = e;
		}

		void renum() {
			int[] p = randomPermutation(n);
			for (Edge e : edges) {
				e.from = p[e.from];
				e.to = p[e.to];
			}
			shuffle();
		}

		void shuffle() {
			for (int i = 0; i < edges.length; i++) {
				int j = random(i + 1);
				Edge e = edges[i];
				edges[i] = edges[j];
				edges[j] = e;
			}
		}

		void print() {
			try {
				++testNum;
				PrintWriter out = new PrintWriter(testNum / 10 + "" + testNum
						% 10);
				out.println(n + " " + edges.length);
				for (Edge e : edges) {
					out.println((e.from + 1) + " " + (e.to + 1) + " " + e.w);
				}
				out.close();
			} catch (Throwable e) {
				throw new AssertionError();
			}

		}
	}

	static final Random rand = new Random(12313L);

	static int[] randomPermutation(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = i;
			int j = rand.nextInt(i + 1);
			int t = a[j];
			a[j] = a[i];
			a[i] = t;
		}
		return a;
	}

	public static void main(String[] args) {
		// Min tests
		genTestRandom(2, 5, 1, 10);
		genTestLine(2, 5, 1, 10);
		genTestStar(2, 5, 1, 10);
		genTestTree(2, 5, 1, 10);
		genTestCircle(2, 5, 1, 10);
		genTestWhole(2, 5, 1, 10);

		// Max tests
		genTestRandom(96, 100, 1, 1000);
		genTestLine(96, 100, 1, 1000);
		genTestStar(96, 100, 1, 1000);
		// genTestAntiDFS(96, 100, 1, 1000);
		// genTestAntiBFS(96, 100, 1, 1000);
		genTestTree(96, 100, 1, 1000);
		genTestCircle(96, 100, 1, 1000);
		genTestWhole(96, 100, 1, 1000);

		// Some other tests
		genTestRandom(10, 70, 500, 1000);
		genTestLine(10, 70, 500, 1000);
		genTestStar(10, 70, 500, 1000);
		// genTestAntiDFS(10, 70, 500, 1000);
		// genTestAntiBFS(10, 70, 500, 1000);
		genTestTree(10, 70, 500, 1000);
		genTestCircle(10, 70, 500, 1000);
		genTestWhole(10, 70, 500, 1000);

		genTestRandom(10, 70, 1, 100);
		genTestLine(10, 70, 1, 100);
		genTestStar(10, 70, 1, 100);
		// genTestAntiDFS(10, 70, 1, 100);
		// genTestAntiBFS(10, 70, 1, 100);
		genTestTree(10, 70, 1, 100);
		genTestCircle(10, 70, 1, 100);
		genTestWhole(10, 70, 1, 100);
	}

	static int random(int l, int r) {
		return rand.nextInt(r - l + 1) + l;
	}

	static int random(int n) {
		return random(0, n - 1);
	}

	static void genTestRandom(int minN, int maxN, int minW, int maxW) {
		int n = random(minN, maxN);
		int m = random(0, n * (n - 1) >> 1);
		HashSet<Edge> was = new HashSet<Edge>();
		Edge[] e = new Edge[m];
		for (int i = 0; i < m; i++) {
			int a = random(n);
			int b = random(n);
			Edge edge = new Edge(a, b, random(minW, maxW));
			Edge rEdge = new Edge(b, a, edge.w);
			while (a == b || was.contains(edge) || was.contains(rEdge)) {
				a = random(n);
				b = random(n);
				edge.from = a;
				edge.to = b;
				rEdge.from = b;
				rEdge.to = a;
			}
			was.add(edge);
			e[i] = edge;
		}
		DSU dsu = new DSU(n);
		for (Edge a : e) {
			dsu.union(a.from, a.to);
		}
		e = copyOf(e, e.length + n);
		for (int i = 1, k = m; i < n; i++) {
			if (dsu.union(i, 0)) {
				e[k++] = new Edge(0, i, random(minW, maxW));
			}
			if (i == n - 1) {
				e = copyOf(e, k);
			}
		}
		Test test = new Test(n, e);
		test.print();
	}

	static void genTestLine(int minN, int maxN, int minW, int maxW) {
		int n = random(minN, maxN);
		int m = n - 1;
		Edge[] e = new Edge[m];
		for (int i = 0; i < m; i++) {
			e[i] = new Edge(i, i + 1, random(minW, maxW));
		}
		Test test = new Test(n, e);
		test.renum();
		test.print();
	}

	static void genTestStar(int minN, int maxN, int minW, int maxW) {
		int n = random(minN, maxN);
		int m = n - 1;
		Edge[] e = new Edge[m];
		for (int i = 0; i < m; i++) {
			e[i] = new Edge(0, i + 1, random(minW, maxW));
		}
		Test test = new Test(n, e);
		test.renum();
		test.print();
	}

	static void genTestTree(int minN, int maxN, int minW, int maxW) {
		int n = random(minN, maxN);
		int m = n - 1;
		Edge[] e = new Edge[m];
		for (int i = 0; i < m; i++) {
			e[i] = new Edge(random(i + 1), i + 1, random(minW, maxW));
		}
		Test test = new Test(n, e);
		test.renum();
		test.print();
	}

	static void genTestCircle(int minN, int maxN, int minW, int maxW) {
		int n = random(minN, maxN);
		int m = n;
		Edge[] e = new Edge[m];
		for (int i = 0; i < n - 1; i++) {
			e[i] = new Edge(i, i + 1, random(minW, maxW));
		}
		e[n - 1] = new Edge(0, n - 1, random(minW, maxW));
		Test test = new Test(n, e);
		test.renum();
		test.print();
	}

	static void genTestWhole(int minN, int maxN, int minW, int maxW) {
		int n = random(minN, maxN);
		int m = n * (n - 1) >> 1;
		Edge[] e = new Edge[m];
		for (int i = 0, k = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++, k++) {
				e[k] = new Edge(i, j, random(minW, maxW));
			}
		}
		Test test = new Test(n, e);
		test.renum();
		test.print();
	}
}
