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

using namespace std;

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

vector<int> h;
vector<int> tata;

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

void Union(int u, int v) {
    int ru = Find(u);
    int rv = Find(v);

    if(ru == rv) {
        return;
    }

    if (h[ru] < h[rv]) {
        tata[ru] = rv;
    } else if (h[ru] == h[rv]) {
        tata[ru] = rv;
        h[rv]++;
    } else if (h[ru] > h[rv]) {
        tata[rv] = ru;
    }

}
vector<vector<int>> kruskal(vector<vector<int>> &muchii, int N, int &cost) {

    vector<vector<int>> rez;

    h.assign(N+1, 0);
    tata.assign(N+1, 0);

    sort(muchii.begin(), muchii.end());

    for (auto& m : muchii) {
        if (Find(m[1]) != Find(m[2])) {
            Union(m[1], m[2]);
            cost += m[0];
            rez.push_back(m);
            if (rez.size() == N-1) {
                break;
            }
        } 
    }

    return rez;
}
int main() {

    int N, M;
    fin >> N >> M;

    vector<vector<int>> muchii;

    for (int i = 0; i < M; i++) {
        int x, y, w;
        fin >> x >> y >> w;
        muchii.push_back({w, x, y});
    }

    int cost = 0;
    vector<vector<int>> rez = kruskal(muchii, N, cost);

    fout << cost << endl;
    fout << rez.size() << endl;
    for (auto m : rez) {
        fout << m[1] << " " << m[2] << endl;
    }

    fin.close();
    fout.close();
    return 0;
}