#include <fstream>
#include<algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;

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

struct asd{
    int x,y,c;
};

int sef[200001],n,m,sum=0,contor=0;

bool cmp(asd p1, asd p2){
    return p1.c < p2.c;
}

int sef_suprem(int x){
    if(sef[x]==x)
        return x;
    else
        return sef[x]=sef_suprem(sef[x]);
}

void unire(int x,int y){
    int sef1=sef_suprem(x);
    int sef2=sef_suprem(y);
    sef[sef1]=sef2;
}



int main(){
    fin>>n>>m;
    vector<asd> muchii,sol;
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        muchii.push_back({x,y,c});
    }
    for(int i=1;i<=n;i++)
        sef[i]=i;
    sort(muchii.begin(),muchii.end(),cmp);
    for(int i=0;i<m&&contor<=n-1;i++){
        if(sef_suprem(muchii[i].x)!=sef_suprem(muchii[i].y)){
            sum+=muchii[i].c;
            contor++;
            sol.push_back(muchii[i]);
            unire(muchii[i].x,muchii[i].y);
        }
    }
    fout<<sum<<endl;
    fout<<contor<<endl;
    for(int i=0;i<contor;i++){
        fout<<sol[i].y<<" "<<sol[i].x<<endl;
    }
    return 0;
}