#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");

struct vecin{
int x,c;};

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

vector <vecin> 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;
vecin v;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=m;i++)
     {
      fscanf(fin,"%d %d %d",&z,&y,&v.c);
      //G[z][ ++G[z][0] ].x=y;
      v.x=y;
      G[z].push_back(v);
      v.x=z;
      G[y].push_back(v);
      //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].x]=G[vfs][i].c;
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].x ]>G[vfmin][i].c && uz[G[vfmin][i].x]==0)
             {
              cmin[ G[vfmin][i].x ]=G[vfmin][i].c;
              prec[ G[vfmin][i].x ]=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]);
}