#include <bits/stdc++.h>
#define nmax 400005

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int ind[nmax],x[nmax],y[nmax],c[nmax],GR[200005];
vector < pair<int,int> > answer;

bool cmp(int i, int j){
    return(c[i]<c[j]);
}

int grupa(int i){
    if(GR[i]==i)
        return i;

    GR[i]=grupa(GR[i]);

    return GR[i];
}

void reuniune(int x, int y){
    GR[grupa(x)]=grupa(y);
}

int main(){
    int n,m,i,ans=0;

    fin>>n>>m;

    for(i=1;i<=n;i++)
        GR[i]=i;

    for(i=1;i<=m;i++){
        fin>>x[i]>>y[i]>>c[i];
        ind[i]=i;
    }

    sort(ind+1,ind+m+1,cmp);

    for(i=1;i<=m;i++){
        if(grupa(x[ind[i]])!=grupa(y[ind[i]])){
            reuniune(x[ind[i]],y[ind[i]]);
            answer.push_back(make_pair(x[ind[i]],y[ind[i]]));
            ans+=c[ind[i]];
        }
    }

    fout<<ans<<"\n"<<answer.size()<<"\n";

    for(i=0;i<answer.size();i++)
        fout<<answer[i].first<<" "<<answer[i].second<<"\n";

	return 0;
}