#include <bits/stdc++.h>

using namespace std;

struct muchie{
    int x,y,cost;
};

muchie v[400001];

int   t[200001];
int sol[200001];

int cmp(muchie a, muchie b){
    if(a.cost<b.cost)
        return 1;
    return 0;
}

int dady(int x){
    if(t[x]==x)
        return x;
    else{
        t[x]=dady(t[x]);
        return t[x];
    }
}

inline void join(int x, int y){
    int tati1, tati2;
    tati1=dady(x);
    tati2=dady(y);
    t[tati2]=tati1;
}

int main()
{
    FILE *fin, *fout;
    int n,m,i,j,c,suma;
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(int z=0;z<m;z++){
        fscanf(fin,"%d%d%d",&i,&j,&c);
        v[z].x=i-1;
        v[z].y=j-1;
        v[z].cost=c;
    }
    for(i=0;i<n;i++){
        t[i]=i;
    }
    sort(v,v+m,cmp);
    int z=0;
    suma=0;
    int count;
    for(count=0;count<n-1;z++){
        i=v[z].x;
        j=v[z].y;
        if(dady(i)!=dady(j)){
            join(i,j);
            suma+=v[z].cost;
            sol[count]=z;
            count++;
        }
    }
    fprintf(fout,"%d\n%d\n",suma,count);
    for(i=0;i<count;i++){
        fprintf(fout,"%d %d\n",v[sol[i]].x+1,v[sol[i]].y+1);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}