#include <cstdio>
#include <algorithm>

using namespace std;
int tata[100002];
struct legaturi {
    int val, n1, n2;
}leg[400002], rez[200002];
bool cmp (legaturi a, legaturi b) {
    return a.val<b.val;
}
int sef(int x) {
    if (x==tata[x]) {
        return x;
    }
    return tata[x]=sef(tata[x]);
}
void uni (int a, int b) {
    int sefa=sef(a);
    int sefb=sef(b);
    tata[sefb]=sefa;
}
int main()
{
    int n, n1, n2, c, i, m, j, total=0;
    FILE *fin, *fout;
    fin=fopen("apm.in" ,"r");
    fout=fopen("apm.out" ,"w");
    fscanf(fin, "%d%d" ,&n ,&m);
    for (i=1;i<=n;i++) {
        tata[i]=i;
    }
    for (i=0;i<m;i++) {
        fscanf(fin, "%d%d%d" ,&n1 ,&n2 ,&c);
        leg[i].val=c;
        leg[i].n1=n1;
        leg[i].n2=n2;
    }
    sort(leg, leg+m, cmp);
   /* for (i=0;i<m;i++) {
            fprintf(fout, "%d %d %d\n" ,leg[i].val ,leg[i].n1 ,leg[i].n2);
    }*/
    j=0;
    for (i=0;i<n-1;i++) {
        if (sef(leg[j].n1)!=sef(leg[j].n2)) {
            uni(leg[j].n1, leg[j].n2);
            total+=leg[j].val;
            rez[i].n1=leg[j].n1;
            rez[i].n2=leg[j].n2;
        }
        else {
            i--;
        }
        j++;
    }
    fprintf(fout, "%d\n%d\n" ,total ,n-1);
    for (i=0;i<n;i++) {
            fprintf(fout, "%d %d\n" ,rez[i].n1 ,rez[i].n2);
    }
    return 0;
}