#include <stdio.h>

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

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

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

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

void del()
{
H[1] = H[lvl];
as[1] = as[lvl];
af[1] = af[lvl];
lvl--;
down(1);
}

int main()
{
FILE *in = fopen("apm.in","r");
FILE *out = fopen("apm.out","w");
int n,m,x,y,c;
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;
}
add(1);
apm[1]=-1;

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


int cost=0;
while (lvl)
{
if (apm[as[1]]==0) {
                   apm[as[1]]=af[1];
                   cost+=H[1];
                   x = as[1];
                   del();
                   add(x);
                   }
else del();
}
fprintf(out,"%d\n%d\n",cost,n-1);
for (int i=2;i<=n;i++) fprintf(out,"%d %d\n",i,apm[i]);
}