#include <stdio.h>

struct nod
{
int x,c;
nod *urm;
};
nod *A[200001];
int apm[400001],H[400001],af[400001],as[400001],lvl;

void percolate(int p)
{
int aux;
while (p>1 && H[p]<H[p/2])
{
aux = H[p];H[p]=H[p/2];H[p/2]=aux;
aux = af[p];af[p]=af[p/2];af[p/2]=aux;
aux = as[p];as[p]=as[p/2];as[p/2]=aux;
}
}

void shift(int p)
{
int ok=1,x,aux;
while (ok)
{
ok=0;
if (2*p<=lvl)
{
x = 2*p;
if (x+1<=lvl && H[x]>H[x+1]) x++;
}
if (H[p]>H[x])
{
ok=1;
aux=H[x];H[x]=H[p];H[p]=aux;
aux=af[x];af[x]=af[p];af[p]=aux;
aux=as[x];as[x]=as[p];as[p]=aux;
p = x;
}
}
}

void put(int p)
{
while (A[p]!=NULL)
{
lvl++;
H[lvl] = A[p]->c;
af[lvl] = p;
as[lvl] = A[p]->x;
percolate(lvl);
A[p] = A[p]->urm;
}
}

int main()
{
FILE *in = fopen("apm.in","r");
FILE *out = fopen("apm.out","w");

int n,i,x,y,c,m;
nod *urm;
fscanf(in,"%d%d",&n,&m);
while (m)
{
m--;
fscanf(in,"%d%d%d",&x,&y,&c);
urm = new nod;
urm->x = y;
urm->c = c;
urm->urm = A[x];
A[x] = urm;
urm = new nod;
urm->x = x;
urm->c = c;
urm->urm = A[y];
A[y] = urm;
}
apm[1]=-1;
put(1);
//put(2);
//for (i=1;i<=lvl;i++) fprintf(out,"%d ",H[i]);


int cost=0;
while (lvl)
{

//for (i=1;i<=lvl;i++) fprintf(out,"%d ",H[i]);
//fprintf(out,"\n");

if (apm[as[1]]==0) {
                   apm[as[1]]=af[1];
                   cost+=H[1];
                   x = as[1];
                   //H[1] = H[lvl];
                   //as[1] = as[lvl];
                   //af[1] = af[lvl];
                   //lvl--;
                   //shift(1);
                   put(x);
                   }
else
{
H[1] = H[lvl];
as[1] = as[lvl];
af[1] = af[lvl];
lvl--;
shift(1);
}
}

fprintf(out,"%d\n%d\n",cost,n-1);
for (i=2;i<=n;i++) fprintf(out,"%d %d\n",i,apm[i]);
}