#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=200420;
const int M=400420;

struct gr{ int x, y, c;}g[M];
int p[N],n,m,drumx[N],drumy[N];
long long sum;


void afisare(){
    FILE *out;
    out=fopen("apm.out","w");
    n--;

    fprintf(out,"%lld\n%d\n",sum,n);
    for(int i=1;i<=n;i++){
        fprintf(out,"%d %d\n",drumx[i],drumy[i]);

    }

}


inline bool cmp(gr x, gr y){
    return (x.c<y.c);
}

inline int  caut(int x){
    if(p[x]==x) return x;
    p[x]=caut(p[x]);
    return p[x];

}
inline bool uneste(int x, int y){
    if(x!=y){
        p[x]=y;
        return 1;
    }
    return 0;

}

void citire(){
    FILE *in;
    in=fopen("apm.in","r");
    fscanf(in,"%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;i++){
        fscanf(in,"%d%d%d",&a,&b,&c);
        g[i].x=a;
        g[i].y=b;
        g[i].c=c;
    }
    sort(g+1,g+m+1,cmp);

}


void rez(){
    int j=1,i=1;
    for(int i=1;i<=n;i++) p[i]=i;
   while(j<n&&i<=m){
        if(uneste(caut(g[i].x), caut(g[i].y))){
            drumx[j]=g[i].x;
            drumy[j]=g[i].y;
            j++;
            //cnt++;
            sum+=g[i].c;
        }
        i++;

    }


}

int main()
{
    citire();
    rez();
    afisare();
    return 0;
}