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

using namespace std;

const int NMAX = 400005;

int h[NMAX], rad[NMAX], sol[NMAX], n, m;

struct str {
    int x, y, c;
};

int find(int x) {
    if (rad[x] != x) {
        rad[x] = find(rad[x]);
    }

    return rad[x];
}

void _union(int x, int y) {
    int radx = find(x);
    int rady = find(y);

    if (radx == rady) {
        return;
    }

    if (h[rady] > h[radx]) {
        rad[radx] = rad[rady];
    } else if (h[rady] < h[radx]) {
        rad[rady] = rad[radx];
    } else {
        rad[radx] = rad[rady];
        h[radx] += 1;
    }
}

bool sortare(str a, str b) {
    return a.c < b.c;
}

str v[NMAX];

int main() {
    ifstream cin("apm.in");
    ofstream cout ("apm.out");

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> v[i].x >> v[i].y >> v[i].c;
    }

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

    cout.flush();

    for (int i = 1; i <= n; i++) {
        rad[i] = i;
        h[i] = 1;
    }

    int nrm = 0, sum = 0, i = 0;

    while (nrm != n - 1 && i <= m) {
        i++;

        if (find(v[i].x) != find(v[i].y)) {
            _union(v[i].x, v[i].y);
            sum += v[i].c;
            nrm ++;
            sol[nrm] = i;
        }
    }

    cout << sum << "\n" << nrm << "\n";

    for (int i = 1; i <= nrm; i++) {
        cout << v[sol[i]].x << " " << v[sol[i]].y << "\n";
    }

    return 0;
}