#include <cstdio>
#include <algorithm>

using namespace std;

struct penor {

    int x;
    int y;
    int cost;
    int used;

} a[400001];

int n, m;
int tata[200001];

struct cmp {

    bool operator() (const penor &a, const penor &b) {
        return a.cost < b.cost;
    }

};

int rad(int x) {

    int L = x;

    while (tata[L] != L)
        L = tata[L];

    while (tata[x] != x) {
        int aux = tata[x];
        tata[x] = L;
        x = aux;
    }

    return L;

}

int main() {

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);

    int nr = 0;
    int cost = 0;

    for (int i = 1; i <= n; i++)
        tata[i] = i;

    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].cost);
        a[i].used = 0;
    }

    sort(a + 1, a + m + 1, cmp());

    for (int i = 1; i <= m; i++) {

        if (rad(a[i].x) != rad(a[i].y)) {
            tata[rad(a[i].x)] = tata[rad(a[i].y)];
            nr++;
            cost += a[i].cost;
            a[i].used = 1;
        }

    }

    printf("%d\n%d\n", cost, nr);

    for (int i = 1; i <= m; i++)
        if (a[i].used)
            printf("%d %d\n", a[i].x, a[i].y);

    return 0;
}