#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// APM - ALGORITMUL LUI KRUSKAL

//ifstream cin ("input"); ofstream cout ("output");
ifstream cin ("apm.in"); ofstream cout ("apm.out");

struct muchie{
    int a, b, cost;
};

bool cmp (muchie ceva, muchie altceva){
    return ceva.cost < altceva.cost; // crescator dupa cost
    // return ceva.cost > altceva.cost; // descrescator dupa cost
}

vector<muchie> v;


vector<int> tata, cardinal;

int gasesteTata(int node){
    if (node != tata[node]) {
        tata[node] = gasesteTata(tata[node]);
    }
    return tata[node];
}

void uneste(int nodA, int nodB) {
    nodA = gasesteTata(nodA);
    nodB = gasesteTata(nodB);
    if (cardinal[tata[nodA]] > cardinal[tata[nodB]]) {
        // torn ce este in B in A
        cardinal[tata[nodA]] += cardinal[tata[nodB]];
        cardinal[tata[nodB]] = 0;
        tata[nodB] = tata[nodA];
    }
    else {
        // torn ce este in A in B
        cardinal[tata[nodB]] += cardinal[tata[nodA]];
        cardinal[tata[nodA]] = 0;
        tata[nodA] = tata[nodB];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin>>n>>m;

    tata.resize(n+1);
    cardinal.resize(n+1);

    for (int i=1; i<=n; i++){
        tata[i] = i;
        cardinal[i] = 1;
    }

    v.resize(m);
    for (int i=0; i<m; i++){
        cin>>v[i].a>>v[i].b>>v[i].cost;
    }

    sort(v.begin(), v.end(), cmp); // sortare de structuri folosind comparator scris de noi

    /*
    for (auto &x : v){
        cout<<x.a<<" "<<x.b<<" "<<x.cost<<'\n';
    }
    */

    int raspuns = 0;
    vector<muchie> muchiiRaspuns;

    for (auto &x : v){
        if (gasesteTata(x.a) == gasesteTata(x.b)){ // a si b sunt deja conectate -> nu mai trag muchie pentu ca as face un ciclu!
            continue;
        }

        uneste(x.a, x.b); // pun muchie
        raspuns += x.cost;
        muchiiRaspuns.push_back(x);
    }

    cout<<raspuns<<'\n';
    cout<<muchiiRaspuns.size()<<'\n';
    for (auto &x : muchiiRaspuns){
        cout<<x.a<<" "<<x.b<<'\n';
    }

    return 0;
}