#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];
}

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

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

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