#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
const int inf = 1<<30;
const int maxn=2000;

int n,cost[maxn][maxn],parinte[maxn],d[maxn],viz[maxn];

void prim(int s)
{
	int i, j,nr=1;
	viz[s] = 1;
	
	for (i = 1; i <= n; i++){
		
		if (cost[s][i] != 0){
			parinte[i] = s;
			d[i] = cost[s][i];
		}
		else d[i] = inf;
	}
	parinte[s] = 0;
	d[s] = 0;

	int min,pmin;

	for (j = 1; j <= n - 1; j++){

		min = inf;
		for (i = 1; i <= n; i++)
			if (d[i] < min && viz[i] == 0){
				min = d[i];
				pmin = i;
			}
		viz[pmin] = 1;

		for (i = 1; i <= n; i++)
			if (d[i] > cost[pmin][i] && cost[pmin][i]!=0 && viz[i]==0 ){
				d[i] =  cost[pmin][i];
				parinte[i] = pmin;
			}

	}
}

int main()
{
	int i, j,k;
	freopen("amp.in", "r", stdin);
	freopen("amp.out", "w", stdout);
	scanf( "%d ", &n);
	while ( scanf("%d %d %d", &i, &j, &k) != EOF)
		cost[i][j] = cost[j][i] = k;
	srand(time(NULL));
	int s = rand() % n;
	prim(s);
	int suma=0;
	for (i = 1; i <= n; i++)
		suma += d[i];
	printf("%d\n%d\n", suma, n - 1);
	for (i = 1; i <= n; i++)
		if(i!=s) printf("%d %d\n", i, parinte[i]);

	return 0;
}