//Author Antonio-Gabriel Sturzu

#include<stdio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#define inf 1001


int main()
{
	int n,cost=0,prev[200001],key[200001],i,min=0,imin=0,**mat,j;
	char viz[200001];
	clock_t time1,time2;
	FILE *f=fopen("apm2.in","r");

	fscanf(f,"%i",&n);
	mat=(int **) calloc(n*n,sizeof(int *));
	for(i=0;i<n;i++)
		mat[i]=(int *) calloc(n,sizeof(int));
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			fscanf(f,"%i",&mat[i][j]);
	}
	fclose(f);
	
	memset(viz,0,sizeof(viz));
	time1=clock();
	key[0]=0;
	for(i=1;i<n;i++)
		key[i]=inf;

	for(;;)
	{
		min=inf;
		for(i=0;i<n;i++)
		{
			if(viz[i]==0 && key[i]<min)
			{
				min=key[i];
				imin=i;
			}
		}
		if(min==inf)
			break;
		viz[imin]=1;
		cost+=min;
		for(i=0;i<n;i++)
		{
			if(viz[i]==0 && mat[imin][i]<key[i])
			{
				prev[i]=imin;
				key[i]=mat[imin][i];
			}
		} 
	}
	time2=clock();
	printf("Au trecut %f secunde \n",(double)(time2-time1)/CLOCKS_PER_SEC);
	f=fopen("apm2.out","w");
	fprintf(f,"%i\n",cost);
	fprintf(f,"%i\n",n-1);
	for(i=1;i<n;i++)
		fprintf(f,"%i %i\n",prev[i]+1,i+1);
	fclose(f);
	for(i=0;i<n;i++)
		free(mat[i]);
	free(mat);
	return 0;
}