#include <fstream>
using namespace std;
# define MAXIM 2000
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,ns,mat[50000][50000],viz[500000],T[500000],C[500000],s;
void APM()
{ int i,j,k,q,nr,min;
    viz[1]=1;
   // k=0;
   // min=MAXIM;
    for(nr=1;nr<=n;nr++)
    {   k=0;
        q=0;
        min=MAXIM;


    for(i=1;i<=n;i++)
     {
         for(j=1;j<=n;j++)
        {
            if((viz[i]==1)&&(viz[j]==0))

                if((mat[i][j]!=0)&&(mat[i][j]<min))
                {


                       min=mat[i][j];
                       k=j;
                       q=i;
                }

        }
     }
        C[k]=min;
        T[k]=q;
        viz[k]=1;


    }
}
int main()
{int a,b,c,x,i;
  in>>n>>m;
  for(i=1;i<=m;i++)
  {
      in>>a>>b>>c;
      if(mat[a][b]==0&&mat[b][a]==0)
      {mat[a][b]=c;
      mat[b][a]=c;
      }
      if(mat[a][b]!=0&&mat[b][a]!=0)
      {
          if(mat[a][b]>c&&mat[b][a]>c)
          {
              mat[a][b]=c;
              mat[b][a]=c;
          }
      }
  }
  in>>ns;
in.close();
APM();
/*for(i=1;i<=n;i++)
    out<<T[i]<<" ";
out<<endl;
for(i=1;i<=n;i++)
        out<<C[i]<<" ";
*/
x=n-1;
s=0;
for(i=1;i<=n;i++)
    s=s+C[i];

out<<s<<endl;
out<<x<<endl;
for(i=2;i<=n;i++)
    out<<i<<" "<<T[i]<<endl;
  out.close();

    return 0;
}