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

using namespace std;

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

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


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 {
        tata[rv] = ru;
    }
} 

vector<pair<int,int>> kruskal(vector<vector<int>> &muchii, int N, int &cost) {
    tata.assign(N+1, 0);
    h.assign(N+1, 0);
    cost = 0;
    vector<pair<int,int>> apm;
    sort(muchii.begin(), muchii.end());

    for (auto& m : muchii) {
        if (Find(m[1]) != Find(m[2])) {
            apm.push_back({m[1], m[2]});
            cost += m[0];
            Union(m[1], m[2]);
        }
    }
    return apm;
}
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<pair<int, int>> rez = kruskal(muchii, N, cost);

    fout << cost << endl;
    fout << rez.size() << endl;
    for (auto& m : rez) {
        fout << m.first << " " << m.second << endl;
    }
    return 0;
}