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

using namespace std;

const int NMAX = 2e5 + 5;
const char nl = '\n';
ifstream fin("apm.in");
ofstream fout("apm.out");
int father [NMAX], rankk[NMAX];
struct edge {
    int x, y, cost;
};

bool greateredge(const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}

int findr(int node) {
    if (father[node] == node) {
        return node;
    }
    father[node] = findr(father[node]);
    
    return father[node];
}

void unite(int x, int y) {
    int rootx = findr(x), rooty = findr(y);
    if (rootx == rooty) return;
    if (rankk[rootx] == rankk[rooty]) {
        father[rootx] = rooty;
        rankk[rooty]++;
    }
    else {
        if (rankk[rootx] < rankk[rooty]) {
            father[rootx] = rooty;
        } else {
            father[rooty] = rootx;
        }
    }

}

vector<edge> g, apm;

int main () {

    int n, m, x, y, z;
    fin >> n >> m;
    for (int i = 0; i < m ; i++) {
        fin >> x >> y >> z;
        g.push_back({x, y, z});
    }
    for (int i = 1; i <= n;i++) {
        father[i] = i;
        rankk[i] = 0;
    }
    int cost_total = 0;
    sort(g.begin(), g.end(), greateredge);
    for (auto it: g) {
        if (findr(it.x) != findr(it.y)) {
            unite(it.x, it.y);
            cost_total += it.cost;
            apm.push_back(it);
        }
    }
    fout << cost_total << nl;
    fout << apm.size() << nl;
    for (auto it: apm) {
        fout << it.x << " " << it.y << nl;
    }

    return 0;
}