#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i,c,l;
int w[200005];
int sol1,rx,ry,x,y,q,r;
pair < int , pair < int,int > > v[400005];
pair<int,int>sol[200005];
int f(int k){
    while(w[k]>0){
        k=w[k];
    }
    return k;
}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        v[i].first=c;
        v[i].second.first=x;
        v[i].second.second=y;
    }
    sort(v+1,v+m+1);
    for(i=1;i<=n;i++){
        w[i]=-1;
    }
    for(i=1;i<=m;i++){
        rx=f(v[i].second.first);
        ry=f(v[i].second.second);
        if(rx!=ry){
            sol[++l].first=v[i].second.first;
            sol[l].second=v[i].second.second;
            sol1+=v[i].first;
                if(w[rx]<w[ry]){
                    w[rx]+=w[ry];
                    w[ry]=rx;
                }
                else{
                    w[ry]+=w[rx];
                    w[rx]=ry;
                }
        }
    }
    fout<<sol1<<"\n";
    fout<<l<<"\n";
    for(i=1;i<=l;i++){
        fout<<sol[i].second<<" "<<sol[i].first<<"\n";
    }
    return 0;
}