#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct A{
    int x,y,c;
};
int n,m,z[200005],ct;
vector <A> M,sol;
void read();
int cmp(A,A);
void kruskal();
void write();
int main(){
    read();
    kruskal();
    write();
    return 0;
}

void read(){
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        A e;
        scanf("%d%d%d",&e.x,&e.y,&e.c);
        M.push_back(e);
    }
    sort(M.begin(),M.end(),cmp);
}

int cmp(A a,A b){
    if (a.c>b.c){
        return 0;
    }
    return 1;
}

void kruskal(){
    int i=0;
    for (int k=1;k<=n;k++){
        z[k]=k;
    }
    int nrm=0;
    while (nrm<n-1){
        int z1=z[M[i].x];
        int z2=z[M[i].y];
        if (z1!=z2){
            sol.push_back(M[i]);
            nrm++;
            ct+=M[i].c;
            if (z1<z2){
                for (int j=1;j<=n;j++){
                    if (z[j]==z2){
                        z[j]=z1;
                    }
                }
            }
            else {
                for (int j=1;j<=n;j++){
                    if (z[j]==z1){
                        z[j]=z2;
                    }
                }
            }
        }
        i++;
    }
}

void write(){
    freopen("apm.out","w",stdout);
    printf("%d\n%d\n",ct,sol.size());
    for (int i=0;i<sol.size();i++){
        printf("%d %d\n",sol[i].y,sol[i].x);
    }
}