#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define pb(a) push_back(a)
using namespace std;
long n,m,i,j,k,sol,m1,m2,n1,n2,nod,x[400000],y[400000],cost[400000],ind[400000];
long c[200000],q[200000],hx[200000],hy[200000];
vector <long> v[200000];
int comp(const void * a, const void * b){
    return (cost[*((long*)a)]-cost[*((long*)b)]);
}
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;++i)
        scanf("%ld %ld %ld",&x[i],&y[i],&cost[i]);
    for (i=1;i<=m;++i){ind[i]=i;c[i]=i;q[i]=1;v[i].pb(i);}
    qsort(ind+1,m,sizeof(long),comp);
    for (i=1;i<=m;++i){
        if (k==n-1)break;
        n1=x[ind[i]];n2=y[ind[i]];
        if (c[n1]!=c[n2]){
           hx[++k]=n1;hy[k]=n2;
           sol+=cost[ind[i]];
           if (c[n1]<c[n2]){m1=c[n1];m2=c[n2];}
           else {m1=c[n2];m2=c[n1];}
           for (j=0;j<q[m2];++j){
               nod=v[m2][j];
               v[m1].pb(nod);q[m1]++;
               c[nod]=m1;
           }
           v[m2].clear();q[m2]=0;
        }
    }
    printf("%ld\n",sol);
    printf("%ld\n",n-1);
    for (i=1;i<n;++i)
        printf("%ld %ld\n",hx[i],hy[i]);
return 0;
}