#include <cstdio>
#include<algorithm>
using namespace std;
#define maxm 400005
#define maxn 200005
struct muchie{int x,y,cost;};
muchie v[maxm];
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
int n,m,x,y,c,nrs,s;
int arb[maxn],t[maxn],nr[maxn];
int compare(const muchie A,const muchie B){
    return A.cost<B.cost;
}
int rad(int s){
    int r;
    for(r=t[s];r!=t[r];r=t[r]);
    return r;
}
void update(int e1,int e2){
    if(nr[e1]<nr[e2]){
        t[e1]=e2;
        nr[e2]+=nr[e1];
    }
    else
        if(nr[e1]==nr[e2]){
            t[e1]=e2;
            nr[e2]++;}
        else
            {t[e2]=e1;
            nr[e1]++;
            }
}
int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].cost);
    sort(v+1,v+m+1,compare);
    for(int i=1;i<=n;i++){
            t[i]=i,nr[i]=1;
    }
    for(int i=1;i<=m && nrs<n-1;i++){
         if(rad(v[i].x)!=rad(v[i].y)){
                nrs++;
                arb[nrs]=i;
                s+=v[i].cost;
                update(rad(v[i].x),rad(v[i].y));
         }
    }
    fprintf(g,"%d\n%d\n",s,nrs);
    for(int i=1;i<=n-1;i++)
            fprintf(g,"%d %d\n",v[arb[i]].x,v[arb[i]].y);
    return 0;
}