#include <bits/stdc++.h>
using namespace std;

#define NMAX 200002

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

vector < pair<int, pair<int, int> > > edges;
vector < pair<int, int> > arb;

int tata[NMAX], pondere[NMAX];

void initDSU(const int N) {

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

int getRoot(int x) {

    int root;

    for (root = x; root != tata[root]; root = tata[root]);

    int aux;

    while (x != tata[x]) {
        aux = tata[x];
        tata[x] = root;
        x = aux;
    }

    return root;
}

void unite(int x, int y) {

    if (pondere[x] > pondere[y])
        tata[y] = x;
    else
        tata[x] = y;

    if (pondere[x] == pondere[y])
        pondere[y]++;
}

int main() {

    int N, M;

    fin >> N >> M;

    initDSU(N);

    int x, y, c;
    while (M--) {

        fin >> x >> y >> c;

        edges.push_back(make_pair(c, make_pair(x, y)));
    }

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

    int APMcost = 0;
    for (auto& edge: edges) {

        x = getRoot(edge.second.first);
        y = getRoot(edge.second.second);

        if (x != y) {
            unite(x, y);
            arb.push_back(edge.second);
            APMcost += edge.first;
        }
    }

    fout << APMcost << "\n" << N - 1 << "\n";

    for (auto& edge: arb)
        fout << edge.first << " " << edge.second << "\n";

    return 0;
}