#include <cstdio>
#include <algorithm>
#define NMAX 200001
#define MMAX 400001
using namespace std;

 int n,m,C[NMAX],Ord[NMAX-1],nrc,cmax;

 struct muchie{

    int m1,m2,cost;

 }M[MMAX];

bool order(const muchie A, const muchie B){

    if(A.cost == B.cost){
        if(A.m1 == B.m1)
            return A.m2 < B.m2;
            return A.m1 < B.m1;
    }
return A.cost < B.cost;

}

void citesc(){

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    scanf("%d%d%d",&M[i].m1,&M[i].m2,&M[i].cost);
    for(int i=1;i<=n;i++)
    C[i] = i;
}

void Kruskal(){

    int i,minim,maxim;

    for(i=1;nrc<n-1;i++){
        if(C[M[i].m1] != C[M[i].m2])
            Ord[++nrc] = i;
        if(C[M[i].m1] <= C[M[i].m2]){

            minim = C[M[i].m1];
            maxim = C[M[i].m2];
        }
        else{

            minim = C[M[i].m2];
            maxim = C[M[i].m1];
        }
            for(int k=1;k<=n;k++)
                if(C[k] == maxim)
                    C[k] = minim;
    }

    for(int i=1;i<=nrc;i++)
        cmax+=M[Ord[i]].cost;

}

void afisez(){

    printf("%d\n",cmax);
    printf("%d\n",nrc);
    for(int i=1;i<=nrc;i++)
        printf("%d %d\n",M[Ord[i]].m1,M[Ord[i]].m2);

}

int main(){

    citesc();
    sort(M+1,M+m+1,order);
    Kruskal();
    afisez();
    return 0;
}