#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, t[200100], rang[200100], mArb, cost;

struct muchie{
    int x, y, c;
} muchii[400100];

struct raspuns{
    int x, y;
} ans[200100];

bool cmp(muchie a, muchie b) {
    return a.c <= b.c;
}

int root(int k) {
    if(t[k] == 0)
        return k;
    t[k] = root(t[k]);
    return t[k];
}

void reunion(int a, int b) {
    if(a != b) {
        if(rang[a] < rang[b])
            t[a] = b;
        else {
            t[b] = a;
            if(rang[a] == rang[b])
                rang[b]++;
        }
    }
}

int main() {
    f >> n >> m;
    for(int i = 0; i < m; i++)
        f >> muchii[i].x >> muchii[i].y >> muchii[i].c;
    sort(muchii, muchii+m, cmp);

    for(int i = 0; i < m && mArb < n-1; i++) {
        int rx = root(muchii[i].x);
        int ry = root(muchii[i].y);
        if(rx != ry) {
            reunion(rx, ry);
            cost += muchii[i].c;
            ans[mArb++] = {muchii[i].x, muchii[i].y};
        }
    }

    g << cost << '\n' << mArb << '\n';
    for(int i = 0; i < mArb; i++)
        g << ans[i].x << ' '<< ans[i].y << '\n';
}