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

int rang[200000], T[200000], i, j, n, m, ct=0;
int x,y,c;
pair<int,pair<int,int> >Mc[200000];
pair <int,int> APM[200000];
int multime(int i){
    if (T[i]==i) return i;
    else multime(T[i]);
}

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++){
        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]=make_pair(x,y);
        cmin+=Mc[i].first;
    }

    printf("%d\n",cmin);
    printf("%d\n",n-1);
    for(i=1;i<=n-1;++i) printf("%d %d\n",APM[i].first,APM[i].second);

    return 0;
}