#include <cstdio>
#include <cctype>
#include <algorithm>

using std::swap;

const int MAX_N = 200000;
const int MAX_M = 400000;
const int MASK = 255;
const int NORM = 1000;
const int BUFFSIZE = 65536;

char buff[BUFFSIZE];
int pos = BUFFSIZE;

inline char GetChar() {
    if (pos == BUFFSIZE) {
        fread(buff, 1, BUFFSIZE, stdin);
        pos = 0;
    }
    return buff[pos++];
}

inline int ReadInt() {
    char c, sign = 0;
    int q = 0;

    do {
        c = GetChar();
        sign |= (c == '-');
    } while (!isdigit(c));

    do {
        q = (10 * q) + (c - '0');
        c = GetChar();
    } while (isdigit(c));

    return q ^ ((q ^ -q) & -sign);
}

struct Edge {
    int u, v;
    int cost;
};

Edge l[MAX_M];
int indx[MAX_M];

int father[MAX_N], height[MAX_N];
int s[MAX_M], ss;

int getFather(int x) {
    int r = x;
    while (father[r] != r) {
        r = father[r];
    }
    while (father[x] != x) {
        int y = father[x];
        father[x] = r;
        x = y;
    }
    return r;
}

void unionSet(int x, int y) {
    if (height[x] == height[y]) {
        height[x]++;
        father[y] = x;
    } else {
        if (height[x] < height[y]) {
            swap(x, y);
        }
        father[y] = x;
    }
}

int main(void) {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m, u, v;
    int cost;

    n = ReadInt(); m = ReadInt();
    for (int i = 0; i < m; i++) {
        l[i].u = ReadInt() - 1; l[i].v = ReadInt() - 1; l[i].cost = ReadInt();
        indx[i] = i;
    }
    fclose(stdin);

    std::sort(indx, indx + m, [] (const int &A, const int &B) {
        return l[A].cost < l[B].cost;
    });

    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 1;
    }

    cost = 0;
    for (int i = 0; i < m; i++) {
        int k = indx[i];
        u = getFather(l[k].u);
        v = getFather(l[k].v);
        if (u != v) {
            unionSet(u, v);
            cost += l[k].cost;
            s[ss++] = k;
        }
    }

    printf("%d\n%d\n", cost, ss);
    for (int i = 0; i < ss; i++) {
        printf("%d %d\n", 1 + l[s[i]].u, 1 + l[s[i]].v);
    }
    fclose(stdout);
    return 0;
}