#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, i;
int dsu[200005];
struct muchie{
    int a, b, cost;
} v[400005];
vector<pair<int, int>> sol;

bool cmp(muchie a, muchie b){
    return a.cost<b.cost;
}

int rad(int nod){
    if(dsu[nod]<=0){
        return nod;
    }

    dsu[nod]=rad(dsu[nod]);
    return dsu[nod];
}

int main()
{
    fin>>n>>m;

    for(i=1;i<=m;i++){
        fin>>v[i].a>>v[i].b>>v[i].cost;
    }

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

    for(i=1;i<=n;i++){
        dsu[i]=-1;
    }

    long long sum=0;
    for(i=1;i<=m;i++){
        //cout<<v[i].a<<" "<<v[i].b<<' ';
        int r1=rad(v[i].a);
        int r2=rad(v[i].b);
        //cout<<v[i].a<<" "<<v[i].b<<" "<<r1<<" "<<r2<<" "<<dsu[r1]<<" "<<dsu[r2]<<'\n';
        if(r1!=r2){
            if(dsu[r1]<dsu[r2]){
                dsu[r1]+=dsu[r2];
                dsu[r2]=r1;
            }else{
                dsu[r2]+=dsu[r1];
                dsu[r1]=r2;
            }
            sum+=v[i].cost;
            sol.push_back({v[i].a, v[i].b});
        }
    }

    fout<<sum<<'\n';
    fout<<sol.size()<<'\n';
    for(i=0;i<sol.size();i++){
        fout<<sol[i].first<<" "<<sol[i].second<<'\n';
    }



    return 0;
}