# include<cstdio>
#include<algorithm>
//#include <utility>
using namespace std;

int APM[200000][1], rang[200000], T[200000], i, j, n, m, ct=0;
int x,y,c;
pair<int,pair<int,int> >Mc[200000];

int multime(int i){
    if (T[i]==i) return i;
    else multime(T[i]);
    //return
}

void reuneste(int i, int j){
    i = multime(i);
    j = multime(j);
    if (i==j) return;
    if (rang[i]>rang[j]) T[j]=i;
    else T[i]=j;
    if(rang[i]==rang[j]) ++rang[j];
}

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n, &m);
    for(i=0;i<m;i++){
        //int c, y, x;
        scanf("%d%d%d",&x,&y,&c);
        Mc[i]=make_pair(c,make_pair(x,y));
    }
    sort(Mc,Mc+m);
    int cmin=0;
    for(i=1;i<=n;i++) T[i]=i,rang[i]=0;
    for (i=0;i<m;i++){
        x=Mc[i].second.first;
        y=Mc[i].second.second;
        c=Mc[i].first;
        if (multime(x)==multime(y)) continue;
        reuneste(x,y);
        ++ct;
        APM[ct][0]=x;
        APM[ct][1]=y;
        cmin+=Mc[i].first;
    }
    printf("%d\n",cmin);
    printf("%d\n",n-1);
    for(i=1;i<=ct;++i) printf("%d %d\n",APM[i][0],APM[i][1]);
/*
    for(i=0;i<m;i++){
        printf("%d %d %d\n",Mc[i].second.first,Mc[i].second.second,Mc[i].first);
    }
*/

    return 0;
}