#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e5;
const int MMAX = 4e5;

struct muchie {
    int x, y, c;
};

muchie a[MMAX + 1], v[MMAX + 1];

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

int h[NMAX + 1], t[NMAX + 1];

void Union(int x, int y) {
    if(h[x] < h[y]) {
        t[x] = y;
    } else {
        if(h[x] > h[y]) {
            t[y] = x;
        } else {
            t[x] = y;
            h[x]++;
        }
    }
}

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


int main() {
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        f >> a[i].x >> a[i].y >> a[i].c;
    }
    sort(a + 1, a + m + 1, cmp);
    for(int i = 1; i <= n; i++) {
        h[i] = 1;
        t[i] = i;
    }
    int sum = 0;
    int nr = 0;
    for(int i = 1; i <= m; i++) {
        int p = Find(a[i].x);
        int q = Find(a[i].y);
        if(p != q) {
            sum += a[i].c;
            Union(p, q);
            nr++;
            v[nr] = a[i];
        }
    }
    g << sum << '\n';
    g << nr << '\n';
    for(int i = 1; i <= nr; i++) {
        g << v[i].x << ' ' << v[i].y << '\n';
    }
    return 0;
}