#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct muchie {
    int x, y;
    long long cost;
    bool operator<(const muchie &other) const {
        return cost > other.cost; // Priority queue as a min-heap based on cost
    }
};

struct nod {
    int parinte, siz;
};

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

vector<nod> v;
vector<pair<int, int>> sol;
long long summax;

int root(int i) {
    if (v[i].parinte == i)
        return i;
    return v[i].parinte = root(v[i].parinte);
}

bool joined(int x, int y) {
    return root(x) == root(y);
}

void join(int x, int y) {
    int rx = root(x), ry = root(y);
    if (v[rx].siz > v[ry].siz)
        swap(rx, ry);
    v[rx].parinte = ry;
    v[ry].siz += v[rx].siz;
}

void add_to_sol(const muchie &t) {
    sol.emplace_back(t.x, t.y);
    summax += t.cost;
}

void print_sol() {
    fout << summax << '\n';
    fout << sol.size() << '\n';
    for (const auto &t : sol)
        fout << t.first << ' ' << t.second << '\n';
}

int main() {
    int n, m;
    priority_queue<muchie> pq;
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        fin >> a >> b >> c;
        pq.push({a, b, c});
    }

    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        v[i] = {i, 1}; // Initialize each node as its own root with size 1
    }

    while (!pq.empty()) {
        muchie t = pq.top();
        pq.pop();
        if (!joined(t.x, t.y)) {
            join(t.x, t.y);
            add_to_sol(t);
        }
    }

    print_sol();
    return 0;
}