#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

#define NMAX 200005

vector<pair<int, pair<int, int>>> G;
vector<pair<int, int>> muchii;
int tata[NMAX], rang[NMAX];
int cost;

int radacina(int nod) {
    if (nod == tata[nod]) {
        return nod;
    }
    return tata[nod] = radacina(tata[nod]);
}

void uneste(int x, int y) {
    if (rang[x] < rang[y]) {
        tata[x] = y;
    } else {
        tata[y] = x;
        if (rang[x] == rang[y]) {
            rang[y]++;
        }
    }
}

void kruskal(int n, int m) {
    for (int i = 1; i <= n; ++i) {
        tata[i] = i;
        rang[i] = 1;
    }

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

    for (int i = 0; i < m; ++i) {
        int x = G[i].second.first;
        int y = G[i].second.second;
        int rad1 = radacina(x);
        int rad2 = radacina(y);

        if (rad1 != rad2) {
            cost += G[i].first;
            muchii.push_back({x, y});
            uneste(rad1, rad2);
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;

        G.push_back({c, {x, y}});
    }

    kruskal(n, m);

    fout << cost << '\n';
    fout << n - 1 << '\n';
    for (auto it : muchii) {
        fout << it.first << ' ' << it.second << '\n';
    }
    return 0;
}