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

public class TestGen {

    static int done = 0;

    static final Random rand = new Random(556668949239L);
    static int[][] edge;
    static int[] p, s, arr;    
    static int NS, NL, N;

    static void print() throws IOException  {
		done++;
		int n = N;
		arr = new int[100100];
		for (int i = 1; i <= n; ++i)
			arr[i] = i;
		for (int i = 1; i <= n; ++i) {
			int t = randFromTo(1, i);
			int y = arr[t];
			arr[t] = arr[i];
			arr[i] = y;
		}
		System.err.println("Generation test #" + done);
		PrintWriter out;
		if (done < 10)
	    	out = new PrintWriter("../tests/0" + String.valueOf(done));
		else
	    	out = new PrintWriter("../tests/" + String.valueOf(done));		
		out.print(n);
		out.print(' ');
		out.print(NS);
		out.print(' ');
		out.println(NL);
		for (int i = 2; i <= n; i++) {
	    	out.print(arr[edge[i][0]]);
			out.print(' ');
			out.print(arr[edge[i][1]]);
			out.print(' ');
			out.println(edge[i][2]);									    
	    }	
		out.close();    
    }
        
    static void genSimple() throws IOException {
		PrintWriter out;
		out = new PrintWriter("../preliminary/01");
		out.println("5 3 2");
		out.print("1 2 1\n2 3 1\n3 5 1\n2 4 2");
		out.close();
		
		out = new PrintWriter("../preliminary/02");
		out.println("2 0 0");
		out.print("1 2 10");
		out.close();
		
		out = new PrintWriter("../preliminary/03");
		out.println("2 1 0");
		out.print("1 2 10");
		out.close();
	}
//1    

    static int randFromTo(int from, int to) {
		return rand.nextInt(to - from + 1) + from;
    }        
    static void genTree(int n, int maxW) {
    	p = new int[100100];
    	s = new int[100100];
    	edge = new int[100100][4];
    	p[1] = 1;
    	for (int i = 2; i <= n; ++i)
    		p[i] = randFromTo(1, i - 1);
    	for (int i = 2; i <= n; ++i) {
    		edge[i][0] = i;
    		edge[i][1] = p[i];
    		edge[i][2] = randFromTo(1, maxW);
    		s[i] = edge[i][2];
    	}    		
    }
    static int[] sum, len;
    static void makeGoodTest(int minN, int maxN, int maxW)  throws IOException  {
    	int n = randFromTo(minN, maxN);
    	sum = new int[100100];
    	len = new int[100100];
    	N = n;
    	genTree(n, maxW);
    	int a = randFromTo(1, n), b = randFromTo(1, n);    	
    	int v1 = a, l = 0, v2 = b;
    	while (v1 != 1) {
    		sum[p[v1]] = sum[v1] + s[v1];
    		len[p[v1]] = len[v1] + 1;
    		v1 = p[v1];
    	}
    	NS = 0; NL = 0;
		while (v2 != 1) {
			if (sum[v2] > 0) {
    			NS = sum[v1] + sum[v2];
    			NL = len[v1] + len[v2];
    			break;
    		}
    		sum[p[v2]] = sum[v2] + s[v2];
    		len[p[v2]] = len[v2] + 1;
    		v2 = p[v2];    		
    	}
    	print();
    }	
    
    static void makeHalfLine() throws IOException {
    	int n = 100000;
    	sum = new int[100100];
    	len = new int[100100];
    	N = n;
    	p = new int[100100];
    	s = new int[100100];
    	edge = new int[100100][4];
    	p[1] = 1;
    	for (int i = 2; i <= n; ++i) {
    		if (i <= n / 2)
    			p[i] = i - 1;
    		else
    			p[i] = randFromTo(1, i - 1);
    	}
    	for (int i = 2; i <= n; ++i) {
    		edge[i][0] = i;
    		edge[i][1] = p[i];
    		edge[i][2] = randFromTo(1, 10000);
    		s[i] = edge[i][2];
    	}    		
    
    	int a = randFromTo(1, n), b = randFromTo(1, n);    	
    	int v1 = a, l = 0, v2 = b;
    	while (v1 != 1) {
    		sum[p[v1]] = sum[v1] + s[v1];
    		len[p[v1]] = len[v1] + 1;
    		v1 = p[v1];
    	}
    	NS = 0; NL = 0;
		while (v2 != 1) {
			if (sum[v2] > 0) {
    			NS = sum[v1] + sum[v2];
    			NL = len[v1] + len[v2];
    			break;
    		}
    		sum[p[v2]] = sum[v2] + s[v2];
    		len[p[v2]] = len[v2] + 1;
    		v2 = p[v2];    		
    	}
    	print();
    
    }
    
    static void makeLine() throws IOException {
    	int sum = 0;    	
    	edge = new int[100100][5];
    	for (int i = 2; i <= 100000; ++i) {
    		edge[i][0] = i;
    		edge[i][1] = i - 1;
    		edge[i][2] = randFromTo(1, 10000);
    		sum += edge[i][2];
    	}    		
    	NL = 100000 - 1;
    	NS = sum;
    	N = 100000;
    	print();
    }

	static void makeRandomTest(int minN, int maxN, int maxW)  throws IOException {
    	int n = randFromTo(minN, maxN);
    	N = n;
    	sum = new int[100000];
    	len = new int[100000];
    	genTree(n, maxW);
    	NS = randFromTo(1, 1000000);
    	if (randFromTo(0, 1) == 1)
    		NL = randFromTo(1, n);
    	else
    		NL = 0;
    	print(); 
    }
    static int pow10(int a) {
    	int ans = 1;
    	while (a --> 0)
    		ans *= 10;
    	return ans;
    }
    static int max(int a, int b) {
    	if (a > b)
    		return a;
    	return b;
    }

    public static void main(String[] args) throws IOException {
		boolean f = (new File("../preliminary")).mkdir();
		f = new File("../tests").mkdir();
		genSimple();
		done = 0;
		// Small testcase n <= 100. Score 20
		for (int i = 1; i <= 8; ++i)
			makeGoodTest(i * 10, 100, max(10, pow10(i/2)));			
		makeRandomTest(1, 100, 1000);
		makeRandomTest(50, 100, 10000);

	
		// Middle testcase n <= 10000. Score 20
		for (int i = 1; i <= 8; ++i)
			makeGoodTest(i * 100, 1000, max(10, pow10(i/2)));			
		makeRandomTest(1, 1000, 1000);
		makeRandomTest(500, 1000, 10000);

		// Big testcase n <= 100000. Score 60
		for (int i = 1; i <= 27; ++i) {
			if (i <= 8)
				makeGoodTest(i * 10000, 100000, max(10, pow10(i/2)));			
			else
				makeGoodTest(100000, 100000, 10000);						
		}
		makeLine();
		makeRandomTest(1, 100000, 1000);
		makeRandomTest(50000, 100000, 10000);
		for (int i = 0; i < 10; ++i) 
			makeHalfLine();		
		return;
    }
}
