#include<fstream>

#define inf 10000
using namespace std;
  ifstream f("apm.in");
  ofstream g("apm.out");
  struct muchie
  {
      int l,c;
  };
  muchie a[200];
long  n,s[200],i,j,k,cost,lin,col,nr;
float min1,c[200][200];
int s1;

void citire()
{

   f>>n;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      if(i==j)
       c[i][j]=0;
     else
      c[i][j]=c[j][i]=inf;
     while(f>>i>>j>>cost)
      c[i][j]=c[j][i]=cost;
}

int main()
{

   citire();
   s[1]=1;
   for(k=1;k<=n-1;k++)
    {
     min1=inf;

      for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
	if(s[i]==1&&s[j]==0&&min1>c[i][j])
	 {
	  min1=c[i][j];
	  lin=i;
	  col=j;
	}
	nr++;
	a[nr].l=lin;
	a[nr].c=col;
      // g<<lin<<" "<<col<<" "<<min1<<"\n";
       s1+=min1;
       s[col]=1;

    }

   // g<<"\n";
    g<<s1<<"\n";
    g<<nr<<"\n";
    for(i=1;i<=nr;i++)
        g<<a[i].l<<" "<<a[i].c<<"\n";

    return 0;
}