#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct muchie{int in, sf, cost;};
muchie v[400001];
muchie val;
int t[200001];
muchie nod[200001];
int tata(int x){
if(t[x]==x)
    return x;
else{
    t[x]=tata(t[x]);
    return t[x];
}
}

void join(int x, int y){
int rx, ry;
rx=tata(x);
ry=tata(y);
t[rx]=ry;
}



bool cmp(muchie a, muchie b){
if(a.cost<=b.cost)
    return true;
else
    return false;
}

int main() {
    FILE *fin, *fout;
    int n, m, a, b, c, i, j, tt, cont=0;

fin = fopen("apm.in", "r");
fout = fopen("apm.out", "w");

fscanf(fin,"%d%d", &n, &m);
for(i=1;i<=m;i++){
    fscanf(fin,"%d%d%d", &a, &b, &c);
    v[i].in=a;
    v[i].sf=b;
    v[i].cost=c;
}
for(i=1;i<=n;i++){
    t[i]=i;
}
sort(v+1, v+m+1, cmp);
j=1;
tt=tata(v[1].in);

for(i=1;i<=m;i++){
if(tata(v[i].in)!=tata(v[i].sf)){
    join(v[i].in, v[i].sf);
    cont+=v[i].cost;
    nod[j].in=v[i].in;
    nod[j].sf=v[i].sf;
    j++;
}


}




fprintf(fout,"%d\n%d", cont, n-1);
fprintf(fout,"\n");
for(i=1;i<j;i++){
        fprintf(fout,"%d %d\n", nod[i].in, nod[i].sf);
}
fclose(fin);
fclose(fout);

    return 0;
}