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

using namespace std;

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

const int NMAX = 2e5 + 5;
int id[NMAX], sz[NMAX];
vector<pair<int, pair<int, int> > > edges;
vector<pair<int, int> > res;

int get_root(int x) {
    if (id[x] == 0) {
        id[x] = x;
        sz[x] = 1;
    }

    if (x == id[x])
        return x;
    id[x] = get_root(id[x]);
    return id[x];
}

void unire(int a, int b) {
    a = get_root(a);
    b = get_root(b);

    if (a == b)
        return;

    if (sz[b] > sz[a])
        swap(a, b);

    sz[a] += sz[b];
    id[b] = a;
}

int main() {

    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        edges.push_back(make_pair(c, make_pair(x, y)));
    }

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

    int total = 0;
    for (auto edge : edges) {
        int cost = edge.first, x = edge.second.first, y = edge.second.second;

        if (get_root(x) != get_root(y)) {
            total += cost;
            unire(x, y);
            res.push_back(make_pair(x, y));
        }
    }

    fout << total << '\n' << res.size() << '\n';
    for (auto edge : res) {
        fout << edge.first << ' ' << edge.second << '\n';
    }


    return 0;
}