#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

#define NMAX 200004
#define MMAX 400004

using namespace std;

struct drum {
    int src;
    int dest;
    int cost;

    bool operator < (const drum& d2) const {
        return cost < d2.cost;
    }

};

int N, M, r, nr;
int c[NMAX];
drum ways[MMAX], out[NMAX];

int Find(int x) {
    int y = x, t;
    while(c[y] != y) {
        y = c[y];
    }

    while(y != x) {
        t = c[x];
        c[x] = y;
        x = t;
    }

    return x;
}

void Unite(int x, int y) {
    x = Find(x);
    y = Find(y);
    c[x] = y;
}

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

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= N; i++) {
        c[i] = i;
    }

    for(int i = 1; i <= M; i++) {
        int x, y, d;
        scanf("%d %d %d", &x, &y, &d);
        ways[i].src = x;
        ways[i].dest = y;
        ways[i].cost = d;
    }

    sort(ways + 1, ways + M + 1);

    for(int i = 1; i <= M; i++) {
        if(Find(ways[i].src) != Find(ways[i].dest)) {
            Unite(ways[i].src, ways[i].dest);
            out[nr] = ways[i];
            nr++;
            r += ways[i].cost;
        }
    }

    printf("%d\n", r);
    printf("%d\n", N - 1);

    for(int i = 0; i < N - 1; i++) {
        printf("%d %d\n", out[i].src, out[i].dest);
    }

    return 0;
}