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

using namespace std;

struct A{
    int x,y,c;
};
int n,m,z[200005],ct,h[200005],tata[200005];
vector <A> M,sol;
void read();
int FIND(int);
void UNION(int,int);
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){
    return a.c<b.c;
}

void kruskal(){
    int i=0;
    for (int k=1;k<=n;k++){
        z[k]=k;
    }
    int nrm=0;
    while (nrm<n-1){
        int z1=FIND(z[M[i].x]);
        int z2=FIND(z[M[i].y]);
        if (z1!=z2){
            nrm++;
            ct+=M[i].c;
            sol.push_back(M[i]);
            UNION(z1,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);
    }
}

void UNION(int x,int y){
    int rx=FIND(x);
    int ry=FIND(y);
    if (h[rx]>=h[ry]){
        tata[ry]=rx;
    }
    else {
        tata[rx]=ry;
    }
    if (h[rx]==h[ry]){
        h[rx]++;
    }
}

int FIND(int x){
    int cx=x;
    while (tata[x]){
        x=tata[x];
    }
    while (tata[cx]){
        int y=tata[cx];
        tata[cx]=x;
        cx=y;
    }
    return x;
}