#include <iostream>
#include <fstream>
// problema: https://www.infoarena.ro/problema/apm
using namespace std;

const int IMAX = 4e5;
int p[IMAX+1], sz[IMAX+1];

int Find(int x) {
    while (x != p[x]){ x = p[x]; }
    return x;
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (sz[x] > sz[y]) {
        p[y] = x;
        sz[x] += sz[y];
    }else {
        p[x] = y;
        sz[y] += sz[x];
    }
}
struct muchie {
    int x,y,c;
};

muchie v[IMAX+1], r[IMAX+1];

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

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m;
    cin >> n >> m;
    for (int i=1; i<=n; ++i) {
        p[i] = i;
        sz[i] = 1;
    }
    for (int i=1; i<=m; ++i) {
        cin >> v[i].x >> v[i].y >> v[i].c;
    }
    sort (v+1, v+m+1,cmp);
    int sum = 0;
    int nr = 0;
    for (int i=1; i<=m; ++i) {
        if (Find(v[i].x) != Find(v[i].y)) {
            nr++;
            r[nr] = v[i];
            sum += v[i].c;
            Union(v[i].x, v[i].y);
            if (nr == n - 1) break;
        }
    }
    cout << sum << '\n';
    // afisati nr de muchii
    cout << nr << '\n';
    // muchiile din apm - muchiile din vectorul r;
    for (int i = 1; i <= nr; ++i)
        cout << r[i].x << " " << r[i].y << '\n';
    return 0;
}