#include <cstdio>
#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];

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 quick_sort(int st, int dr){

    if(st<dr){
        int i = st , j = dr;
        muchie x = M[st];

            while(i<j){

                while(i<j && M[j].cost >= x.cost) j--;
                M[i] = M[j];
                while(i<j && M[i].cost <= x.cost) i++;
                M[j] = M[i];
            }
                M[i] =x;

    quick_sort(st,i-1);
    quick_sort(i+1,dr);
    }
}

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();
    quick_sort(1,m);
    Kruskal();
    afisez();
    return 0;
}