#include <bits/stdc++.h>

int tata[200001];
std::vector < std::pair < int, int > > muchii;

struct stra {
    int a, b, c;
} v[400000];

bool compar(stra a, stra b){
    return a.c<b.c;
}

int sef(int a){
    if(tata[a]!=a)
        tata[a]=sef(tata[a]);

    return tata[a];
}

void join(int a, int b){
    int x, y;
    x=sef(a);
    y=sef(b);
    tata[x]=y;
}

int main(){
    FILE *fin, *fout;
    int n, m, i, cost=0, j;
    fin=fopen("apm.in", "r");
    fout=fopen("apm.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=0;i<m;i++)
        fscanf(fin, "%d%d%d", &v[i].a, &v[i].b, &v[i].c);
    std::sort(v, v+m, compar);
    for(i=1;i<=n;i++)
        tata[i]=i;
    for(i=0;i<m;i++){
        if(sef(v[i].a)!=sef(v[i].b)){
            cost+=v[i].c;
            muchii.push_back({v[i].a, v[i].b});
            join(v[i].a, v[i].b);
        }
    }
    fprintf(fout, "%d\n%d\n", cost, muchii.size());
    for(i=0;i<muchii.size();i++)
        fprintf(fout, "%d %d\n", muchii[i].first, muchii[i].second);
    fclose(fin);
    fclose(fout);

    return 0;
}