#include <cstdio>
#include <algorithm>
using namespace std;
 
 
struct edge{int a;
            int b;
            int cost;
            };
 
edge G[400005],sol[200000];
int minim,maxim,i,j,num,n,m,tata[200005],h[200005];
int c;
 
void combine_Heap(int rad,int n){
    int tata,fiu;
    edge x=G[rad];
    tata=rad;
    fiu=rad*2;
 
    while(fiu<=n){
        if(fiu+1<=n)
        if(G[fiu].cost>G[fiu+1].cost){
 
            fiu=fiu+1;
 
        }
        if(x.cost>G[fiu].cost){
 
            G[tata]=G[fiu];
            tata=fiu;
            fiu=2*tata;
 
        }
        else{
            break;
 
        }
 
    }
    G[tata]=x;
 
}
 
edge extractmin(int &n){
 
    edge x=G[1];
 
    G[1]=G[n];
    --n;
    combine_Heap(1,n);
    return x;
 
}
int find(int x){
 
    int rad,aux;
 
    rad=x;
 
    while(tata[rad]){
 
        rad=tata[rad];
 
    }
    while(tata[x]){
 
        aux=x;
        x=tata[x];
        tata[aux]=rad;
 
    }
 
    return rad;
 
}
void uni(int a,int b){
 
    if(h[b]>h[a]){
 
        tata[a]=b;
 
    }
    else{
 
        tata[b]=a;
        if(h[a]==h[b])
 
            ++h[a];
 
    }
 
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
 
    scanf("%d%d",&n,&m);
 
    for(i=1;i<=m;++i){
 
        scanf("%d%d%d",&G[i].a,&G[i].b,&G[i].cost);
    }
    for(i=m/2;i>0;--i){
 
        combine_Heap(i,m);
 
    }
	//
    int f1,f2;
    while(num<n-1){
 
        edge muchie=extractmin(m);
 
        f1=find(muchie.a);
        f2=find(muchie.b);
 
        if(f1!=f2){
 
            sol[++num]=muchie;
            c+=muchie.cost;
            uni(f1,f2);
 
        }
		else{
			--i;
			
		}
    }
    printf("%d\n%d\n",c,num);
    for(i=1;i<=n-1;++i){
 
        printf("%d %d\n",sol[i].a,sol[i].b);

    }
    return 0;
}