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

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

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

struct muchie{
    int x, y, c;
} muchii[400001], muchiiArb[200001];

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

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

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



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++) {
        if(root(muchii[i].x) != root(muchii[i].y)) {
            reunion(muchii[i].x, muchii[i].y);
            cost += muchii[i].c;
            muchiiArb[mArb++] = muchii[i];
        }
    }

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