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

using namespace std;

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

int N, M, cost_arbore, nr_muchii;
struct muchie {
    int u, v, cost;
};

int set_find(vector<int> &tati, int nod) {
    if(tati[nod] == 0) return nod;
    tati[nod] = set_find(tati, tati[nod]);
    return tati[nod];
}

void set_union(vector<int> &tati, vector<int> &inaltime, int u, int v) {
    int a = set_find(tati, u);
    int b = set_find(tati, v);
    if(a != b) {
        if(inaltime[a] > inaltime[b]) {
            tati[b] = a; 
        } else if (inaltime[a] < inaltime[b]) {
            tati[a] = b;
        } else {
            inaltime[b] += 1;
            tati[b] = a;
        }
    }
}


int main() {
    fin >> N >> M;
    vector<muchie> muchii(M+1, {0, 0, 0});
    vector<int> tati(N+1, 0);
    vector<int> inaltime(N+1, 0);
    vector<pair<int, int>> arbore_partial;

    for(int i = 1; i <= M; i++) {
        int u, v, cost;
        fin >> u >> v >> cost;
        muchii[i] = {u, v, cost};
        // cout << u << " " << v << " " << cost << "\n";
    }


    sort(muchii.begin() + 1, muchii.end(), [](muchie a, muchie b) {
        return a.cost < b.cost;
    });

    for(int i = 1; i <= M; i++) {
        muchie c = muchii[i];
        // cout << c.u << " " << c.v << " " << c.cost << "\n";
        if(set_find(tati, c.u) != set_find(tati, c.v)) {
            set_union(tati, inaltime, c.u, c.v);
            cost_arbore += c.cost;
            nr_muchii += 1;
            // cout << c.u << " " << c.v << "\n";
            arbore_partial.emplace_back(c.u, c.v);
            if(nr_muchii == N-1) break;
        }
    }

    fout << cost_arbore << "\n";
    fout << nr_muchii << "\n";
    for(pair<int, int> x : arbore_partial) {
        fout << x.first << " " << x.second << "\n";
    }

    return 0;
}