#include <cstdio>
#include <vector>
#define NMAX 200005
#define MMAX 400005
#define INF 2000005

using namespace std;

FILE*fin=fopen("apm.in","r");
FILE*fout=fopen("apm.out","w");


void citire();
void init();
void prim();
void afisare();

vector <int> G[NMAX];
vector <int> CG[NMAX];
int n,m,cost,vfs;
int cmin[NMAX],prec[NMAX],uz[NMAX];

int main()
{
citire();
init();
prim();
afisare();
    return 0;
}

void citire()
{
int i,z,y,cost;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=m;i++)
     {
      fscanf(fin,"%d %d %d",&z,&y,&cost);
      //G[z][ ++G[z][0] ].x=y;
      G[z].push_back(y);
      G[y].push_back(z);
      CG[z].push_back(cost);
      CG[y].push_back(cost);
     }
}

void init()
{
int i;
vfs=1;
for (i=0;i<G[vfs].size();i++)
     cmin[ G[vfs][i]]=CG[vfs][i];
for (i=2;i<=n;i++)
    {
     if (cmin[i]==0) cmin[i]=INF;
     prec[i]=vfs;
    }
uz[vfs]=1;
}

void prim()
{
int i,k,minim,vfmin;
for (k=1;k<=n-1;k++)
    {
     minim=INF; vfmin=INF;
     for (i=2;i<=n;i++)
          if (uz[i]==0 && cmin[i]<minim)
              {minim=cmin[i];vfmin=i;}
     uz[vfmin]=1;
     for (i=0;i<G[vfmin].size();i++)
          if (cmin[ G[vfmin][i] ]>CG[vfmin][i] && uz[G[vfmin][i]]==0)
             {
              cmin[ G[vfmin][i] ]=CG[vfmin][i];
              prec[ G[vfmin][i] ]=vfmin;
             }
    }
for (i=1;i<=n;i++)
     cost+=cmin[i];
}

void afisare()
{
int i;
fprintf(fout,"%d\n",cost);
fprintf(fout,"%d\n",n-1);
for (i=1;i<=n;i++)
     if (i!=vfs)
         fprintf(fout,"%d %d\n",i,prec[i]);
}