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

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

struct Muchie{
    int a, b, w;

};

vector<int> tata(200001, 0), h(200001, 0);

int Find(int u){
    if (tata[u] == u)
        return u;
    tata[u] = Find(tata[u]);
    return tata[u];
}

void Union(int u, int v){
    u = Find(u);
    v = Find(v);
    if (h[u] > h[v]){
        tata[v] = tata[u];
    }
    else {
        tata[u] = tata[v];

        if (h[u] == h[v]){
            h[v]++;
        }
    }
}


int main(){
    int n, m;
    fin >> n >> m;
    vector<Muchie> muchii;
    vector<Muchie> apcm;
    int x, y, c;
    while (fin >> x >> y >> c){
        Muchie m;
        m.a = x;
        m.b = y;
        m.w = c;
        muchii.push_back(m);
    }

    sort(muchii.begin(), muchii.end(), [](Muchie x, Muchie y){
        return x.w < y.w;
    });

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

    int cnt = 0; // cate muchii sunt in arbore
    int costTotal = 0;
    for (Muchie m : muchii){
        if (Find(m.a) != Find(m.b)){
            Union(m.a, m.b);

            apcm.push_back(m);
            costTotal += m.w;
            cnt++;
            if (cnt == n - 1){
                break;
            }
        }
    }

    fout << costTotal << endl;
    fout << apcm.size() << endl;
    for (Muchie m : apcm){
        fout << m.a << " " << m.b << endl;
    }

}