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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector<pair<int, pair<int,int>>> graf;
int parinti[200001];
int radacina(int nod){
    if (parinti[nod] != 0) {
        parinti[nod] = radacina(parinti[nod]);
        return parinti[nod];
    }
    return nod;
}
int costminim = 0;
vector<pair<int,int>> solutie;
int main() {

    int n, m;
    f>>n>>m;
    for(int i = 1; i<=m; i++) {
        int x, y, cost;
        f >> x >> y >> cost;
        graf.emplace_back(cost, make_pair(x, y));
    }
    sort(graf.begin(), graf.end());
//    for(auto &i : graf){
//        cout<<i.second.first<< " "<< i.second.second<<" cu costul "<< i.first <<"\n";
//    }
    for(auto &pereche:graf)
    {
        int nod1 = pereche.second.first;
        int nod2 = pereche.second.second;
        int rad1 = radacina(nod1);
        int rad2 = radacina(nod2);
        if(rad1 != rad2) {
            costminim += pereche.first;
            parinti[rad2] = rad1;
            solutie.emplace_back(nod1, nod2);
        }
    }
    g<<costminim<<"\n";
    g<<solutie.size()<<"\n";
    for(auto &pereche:solutie){
        g<<pereche.first<<" "<<pereche.second<<"\n";
    }
    return 0;
}