#include <iostream>
#include <fstream>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int *t, *muchiev;

struct muchii {
int *x, *y, *c;
};

int radacina(int x) {
if (x!=t[x]) return (t[x]=radacina(t[x]));
else return x;
}

int main() {
int n, m, i, j, aux, suma=0, k=0, l=0;
muchii muchie;
in >> n >> m;
muchie.x=new int[m+1];
muchie.y=new int[m+1];
muchie.c=new int[m+1];
t=new int[m+1];
muchiev=new int[2*m+1];
for (i=1; i<=m; i++)
    in >> muchie.x[i] >> muchie.y[i] >> muchie.c[i];
for (i=1; i<=m-1; i++)
    for (j=i+1; j<=m; j++) {
        if (muchie.c[i]>muchie.c[j]) {
            aux=muchie.x[i];
            muchie.x[i]=muchie.x[j];
            muchie.x[j]=aux;
            aux=muchie.y[i];
            muchie.y[i]=muchie.y[j];
            muchie.y[j]=aux;
            aux=muchie.c[i];
            muchie.c[i]=muchie.c[j];
            muchie.c[j]=aux;
        }
    }
for (i=1; i<=m; i++)
    t[i]=i;
/*for (i=1; i<=m; i++)
    out << muchie.x[i] << " " << muchie.y[i] << " " << muchie.c[i] << endl;*/
for (i=1; i<=m; i++) {
    if (radacina(muchie.x[i])!=radacina(muchie.y[i])) {
        t[radacina(muchie.y[i])]=radacina(muchie.x[i]);
        suma=suma+muchie.c[i];
        muchiev[++k]=muchie.x[i];
        muchiev[++k]=muchie.y[i];
        l++;
    }
}
out << suma << endl << l << endl;
for (i=1; i<=k; i++) {
    out << muchiev[i] << " ";
    if (i%2==0) out << endl;
}
return 0;}
//examen: problema cu operatii pe biti