#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
const int nmax = 2e5;
int n, m;
struct muchie {
    int first, second, cost;
};
vector< muchie > muchii;

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


vector< pair<int, int> > muchii_apm;
int cost_total = 0;
int t[nmax + 1], dim[nmax + 1];

int find(int u)
{
    while(u != t[u]) {
        u = t[u];
    }
    return u;
}   


void merge(int u, int v) {
    int root_u = find(u);
    int root_v = find(v);

    if (dim[root_u] < dim[root_v]) {
        t[root_u] = root_v;
        dim[root_u] ++;
    } else {
        t[root_v] = root_u;
        dim[root_v] ++;
    }
}

int main() {
    citire();

    for(int i = 1; i <= n; i ++) {
        t[i] = i;
        dim[i] = 1;
    }

    sort(muchii.begin(), muchii.end(), [](const muchie &a, const muchie &b){
        return b.cost > a.cost;
    });

    for (auto &muchie : muchii) {
        int u = muchie.first, v = muchie.second, cost = muchie.cost;

        int root_u = find(u), root_v = find(v);

        if(root_u != root_v) {
            cost_total += cost;
            muchii_apm.push_back({u, v});
            merge(u, v);
        }
    }

    fout << cost_total << endl;
    fout << muchii_apm.size() << endl;
    for(auto &m : muchii_apm) {
        fout << m.first << ' ' << m.second << endl;
    }
    return 0;
}