// arbore.cpp : main project file.

#include "iostream"
#include "stdio.h"
using namespace std;


struct { int x,y,c; } arce[400005], solutie[400005];
int nn,na,pl,so, nsolutie;
int S[200005];

void citesteGraf() {
FILE *fi;
int i;
fi = fopen("apm.in","r");
fscanf(fi,"%d %d",&nn,&na);
for (i=0; i<na; i++)
    fscanf(fi,"%d %d %d",&arce[i].x,&arce[i].y,&arce[i].c);
fclose(fi);
}

void arboreCostMin() {


FILE *fi;
fi = fopen("apm.out","w");

int x,y,xx,yy,k,c,cm,ca,i;
for (x=1; x<=nn; x++) S[x] = 0;
S[1] = 1; ca = 0;
for (k=1; k<nn; k++) {
    cm = 2000000000;
    xx = yy = -1;
    for (i=0; i<na; i++) {
        x = arce[i].x;  y = arce[i].y;
        c = arce[i].c;
        if (S[x]!=S[y])
           if (c<cm) {
              xx = x;  yy = y;  cm = c;
           }
	    }

    ++nsolutie;
    solutie[nsolutie].x = xx;
    solutie[nsolutie].y = yy;
    solutie[nsolutie].c = cm;

	S[xx] = S[yy] = 1;
    ca += cm;
    }
fprintf(fi, "%d\n%d\n", ca, nsolutie);
for(k=1; k<=nsolutie; ++k)
  fprintf(fi, "%d %d\n", solutie[k].y, solutie[k].x);

fclose(fi);
}

int main() {
citesteGraf();
arboreCostMin();
return 0;
}