#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;
 
void insertionSort(int lo, int hi) {
    for (int i = lo + 1; i < hi; i++) {
        int x = indx[i];
        int j = i;
        while ((j > lo) && (l[indx[j - 1]].cost > l[x].cost)) {
            indx[j] = indx[j - 1];
            j--;
        }
        indx[j] = x;
    }
}
 
void radixPass(int lo, int hi, int bits) {
    int start[MASK + 1], ptr[MASK + 1];
 
    for (int i = 0; i <= MASK; i++) {
        ptr[i] = 0;
    }
    for (int i = lo; i < hi; i++) {
        ptr[(l[indx[i]].cost >> bits) & MASK]++;
    }
    start[0] = lo;
    ptr[0] += lo;
    for (int i = 1; i <= MASK; i++) {
        start[i] = ptr[i - 1];
        ptr[i] += ptr[i - 1];
    }
    for (int i = 0; i <= MASK; i++) {
        while (start[i] != ptr[i]) {
            int elem = indx[start[i]];
            int bucket = (l[elem].cost >> bits) & MASK;
            while (bucket != i) {
                int tmp = indx[start[bucket]];
                indx[start[bucket]++] = elem;
                elem = tmp;
                bucket = (l[elem].cost >> bits) & MASK;
            }
            indx[start[i]++] = elem;
        }
    }
    if (bits) {
        for (int i = 0; i <= MASK; i++) {
            int siz = ptr[i] - (i ? ptr[i - 1] : lo);
            if (siz > 100) {
                radixPass(ptr[i] - siz, ptr[i], bits - 8);
            } else if (siz > 1) {
                insertionSort(ptr[i] - siz, ptr[i]);
            }
        }
    }
}
 
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() + NORM;
        indx[i] = i;
    }
    fclose(stdin);
 
    radixPass(0, m, 24);
 
    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 - NORM;
            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;
}