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

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

const int NMAX = 400005;
int n, m, i, cost_total, k, tt[NMAX], rang[NMAX];
pair <int, int> arbore[NMAX];

struct muchie {
    int x, y, cost;
} v[NMAX];

bool compare_by_cost (muchie a, muchie b) {
    return a.cost < b.cost;
}

int find_root (int nod) {
    while (tt[nod] != nod)
        nod = tt[nod];
    return nod;
}

void unire (int x, int y) {
    if (rang[x] > rang[y])
        tt[y] = x;

    if (rang[x] < rang[y])
        tt[x] = y;

    if (rang[x] == rang[y]) {
        tt[x] = y;
        rang[y]++;
    }
}

int main() {
    fin >> n >> m;

    for (i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;

    sort (v + 1, v + m + 1, compare_by_cost);

    for (i = 1; i <= n; i++) {
        tt[i] = i;
        rang[i] = 1;
    }

    for (i = 1; i <= m; i++) {
        if (find_root(v[i].x) != find_root(v[i].y)) {
            unire(find_root(v[i].x), find_root(v[i].y));

            arbore[++k].first = v[i].x;

            arbore[k].second = v[i].y;

            cost_total += v[i].cost;
        }
    }

    fout << cost_total << endl;

    fout << n - 1 << endl;

    for (i = 1; i <= k; i++)
        fout << arbore[i].first << " " << arbore[i].second << endl;
}