#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 200010
#include <vector>
#include <iterator>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
class muchie{
public:
    int m1,m2,cost;
    muchie(int a,int b,int c): m1{a},m2{b},cost{c}{}
};
int n,m;
int TT[NMAX],G[NMAX];
vector<muchie> muchii;
vector<muchie> sol;
int find(int x){
    int R,y;
    for(R=x;TT[R]!=R;R=TT[R]);
    //compress
    while(TT[x]!=x){
        y=TT[x];
        TT[x]=R;
        x=y;
    }
    return R;
}

void uneste(int x,int y){
    if(G[x] > G[y])
        TT[y] = x;
    else TT[x] = y;
    if(G[x] == G[y])
        G[y]++;
}

void initPMJ(){
    for(int i=1;i<=n;i++){
        TT[i] = i;
        G[i]=1;
    }
}

void readM(){
    int a,b,c;
    for(int i=1;i<=m;i++){
        f >> a >> b >> c;
        muchii.push_back(muchie(a,b,c));
    }
}

int main()
{
    int nrM=0,cost=0;
    f >> n >> m;
    initPMJ();
    readM();
    sort(muchii.begin(),muchii.end(),[](muchie a,muchie b){return a.cost < b.cost;});
    for(int i=0;i<m;i++){
        if(find(muchii[i].m1) != find(muchii[i].m2)){
            uneste(find(muchii[i].m1) , find(muchii[i].m2));
            nrM++;
            cost += muchii[i].cost;
            sol.push_back(muchii[i]);
        }
    }
    g << cost << '\n' << nrM << '\n';
    for(int i=0;i<sol.size();i++){
        g << sol[i].m1 << ' ' << sol[i].m2 << '\n';
    }
    return 0;
}