#include <cstdio>
#include <algorithm>

using namespace std;

int h[200007], T[200007] , c[200007], m , n , xi , yi , nr , num ;

struct apm {
    int x, y, cost;
};

apm a[400007];

bool cmp(apm b, apm c) {
    return b . cost < c . cost;
}

int father(int i) {
    if(i == T[i]) {
        return i;
    }
    return father(T[i]);
}

int unite(int i, int j) {
    i = father(i);
    j = father(j);
    if(i == j) {
        return 0;
    }
    if(h[i] == h[j]) {
        ++h[i];
        T[i] = i;
    }
    if(h[i] < h[j]) {
        T[i] = j;
    }
    else {
        T[j] = i;
    }
    return 1 ;
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1 ; i <= m ; ++i) {
        scanf("%d %d %d\n", &a[i].x , &a[i].y, &a[i].cost);
    }
    for(int i = 1; i <= n; ++i) {
        T[i] = i;
    }
    sort(a + 1, a + m + 1, cmp );
    for(int i = 1 ; i <= m ; ++i) {
        xi = father(a[i]. x);
        yi = father(a[i].y);
        if(xi != yi && num <= n - 1) {
            int k;
            ++ num;
            nr += a[i].cost;
            k = unite(a[i].x, a[i].y);
            c[num] = i;
        }
    }
    printf("%d\n", nr);
    printf("%d\n", num);
    for(int i = 1; i <= num; ++i) {
        printf("%d %d\n", a[c[i]].x, a[c[i]]. y);
    }
    return 0 ;
}