#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int NMAX = 400000;

struct muchie {

    int x, y, cost;
};

vector <muchie> muchii;
vector <muchie> apm;
bool cmp(muchie a, muchie b) {
    return a.cost < b.cost;
}

int h[NMAX + 2], tata[NMAX + 2];

int findt(int x) {

    for( ; tata[x] != x; x = tata[x]);

    return x;
}

void Union(int x, int y) {

    if(h[x] > h[y])
        tata[y] = x;
    else
        if(h[x] == h[y]) {
            h[x] ++;
            tata[y] = x;
        }
        else
            tata[x] = y;
}

int main() {

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

    int n, m, costminim = 0, x, y, tx, ty;
    muchie aux;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &aux.x, &aux.y, &aux.cost);
        muchii.push_back(aux);
    }

    for(int i = 1; i <= n; i++)
        tata[i] = i;
    sort(muchii.begin(), muchii.end(), cmp);
    for(int i = 0; i < m; i++)
    {
        x = muchii[i].x;
        y = muchii[i].y;
        tx = findt(x);
        ty = findt(y);
        if(tx != ty) {
            costminim += muchii[i].cost;
            Union(tx, ty);
            apm.push_back(muchii[i]);
        }
    }

    printf("%d\n%d\n",costminim, apm.size());

    for(int i = 0; i < apm.size(); i++) {
        printf("%d %d\n",apm[i].x, apm[i].y);
    }

    return 0;
}