#include<fstream>
#include<algorithm>
using namespace std;
int t[200003], n, m, i, soll, ra, rb, nrsol;
struct x3{
    int cost;
    int a;
    int b;
};
pair <int, int> sol[200003];
x3 x[200003];
int cmp(x3 x, x3 y){
    if(x.cost==y.cost){
        if(x.a==y.a)
            return x.b<y.b;
        return x.a<y.b;
    }
    return x.cost<y.cost;
}
int rad(int x){
    while(t[x]>0)
        x=t[x];
    return x;
}
ifstream in("apm.in");
ofstream out("apm.out");
int main(){
    in>>n>>m;
    for(i=1; i<=m; i++)
        in>>x[i].a>>x[i].b>>x[i].cost;
    sort(x+1, x+m+1, cmp);
    for(i=1; i<=n; i++)
        t[i]=-1;
    for(i=1; i<=m; i++){
        ra=rad(x[i].a);
        rb=rad(x[i].b);
        if (ra == rb)
            continue;
        soll+=x[i].cost;
        sol[++nrsol].first=x[i].a;
        sol[nrsol].second=x[i].b;
        if(t[ra]<t[rb]){
            t[ra]+=t[rb];
            t[rb]=ra;
        }else{
            t[rb]+=t[ra];
            t[ra]=rb;
        }
    }
    out<<soll<<"\n";
    out<<nrsol<<"\n";
    for(i=1; i<=nrsol; i++)
        out<<sol[i].first<<" "<<sol[i].second<<"\n";
return 0;
}