#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int MAXN = 200000 + 5;

vector<pair<int,pair<int,int> > >muchii;
int n,m,inaltime[MAXN],tata[MAXN];

int gaseste(int nod){
    int stapan,copie = nod;
    while(tata[nod] != nod)
        nod = tata[nod];
    stapan = nod;
    nod = copie;
    while(nod != tata[nod]){
        copie = nod;
        nod = tata[nod];
        tata[copie] = stapan;
    }
    return stapan;
}
void uneste(int nod1,int nod2){
    int stapan1 = gaseste(nod1),stapan2 = gaseste(nod2);
    if(inaltime[stapan1] > inaltime[stapan2])
        tata[stapan2] = stapan1;
    else if(inaltime[stapan2] > inaltime[stapan1])
        tata[stapan1] = stapan2;
    else{
        tata[stapan1] = stapan2;
        inaltime[stapan1]++;
    }
}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; i++){
        int x,y,cost;
        in>>x>>y>>cost;
        muchii.push_back({cost,{x,y}});
    }
    sort(muchii.begin(),muchii.end());
    for(int i = 1; i <= n; i++){
        tata[i] = i;
        inaltime[i] = 1;
    }
    int cost_minim = 0;
    vector<pair<int,int> > arbore;
    for(int i = 0; i < muchii.size(); i++){

        int nod1 = muchii[i].second.first,nod2 = muchii[i].second.second;
        int cost = muchii[i].first;
        if(gaseste(nod1) != gaseste(nod2)){
            arbore.push_back({nod1,nod2});
            cost_minim += cost;
            uneste(nod1,nod2);
        }
    }
    out<<cost_minim<<"\n"<<arbore.size()<<"\n";
    for(auto muchie : arbore)
        out<<muchie.first<<" "<<muchie.second<<"\n";
    return 0;
}