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

int const INF=1e9;
int n, m, i, t, a, b;
int dsu[200005], rang[200005];

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

void join(int x, int y){
    int rx=radacina(x);
    int ry=radacina(y);

    if(rang[rx]<=rang[ry]){
        dsu[rx]=ry;
        rang[ry]+=rang[rx];
    }else{
        dsu[ry]=rx;
        rang[rx]+=rang[ry];
    }
}

struct muchie{
    int a, b, cost;
} v[400005];
vector<muchie> sol;

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

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

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

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

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


    long long sum=0;
    for(i=1;i<=m;i++){
        if(radacina(v[i].a)!=radacina(v[i].b)){
            join(v[i].a, v[i].b);
            sol.push_back(v[i]);
            sum+=v[i].cost;
        }
    }

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



    return 0;
}