// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

//DSU

//1. Unim arborele mai mic (de inaltime) de arborele mai mare - reuniune
//2. Compresia drumului

const int NMAX = 2e5;
int p[NMAX + 1]; //parintele nodului i
int h[NMAX + 1]; //inaltimea subarborelui lui i

const int MMAX = 4e5;
struct muchie {
    int x, y, c;
};

muchie a[MMAX + 1];
muchie sol[NMAX + 1];

int Find(int x) {//radacina arborelui lui x
    int rad = x;
    while(rad != p[rad]) {
        rad = p[rad];
    }
    while(x != rad) {
        int y = p[x];
        p[x] = rad;
        x = y;
    }
    return rad;
}

void Union(int x, int y) {
    int r1 = Find(x);
    int r2 = Find(y);
    if(r1 != r2) {
        if(h[r1] > h[r2]) {
            p[r2] = r1;
        } else {
            if(h[r1] < h[r2]) {
                p[r1] = r2;
            } else {
                p[r2] = r1;
                h[r1]++;
            }
        }
    }
}

bool cmp(muchie p, muchie q) {
    return p.c < q.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;
        h[i] = 1;
    }
    for(int i = 1; i <= m; i++) {
        cin >> a[i].x >> a[i].y >> a[i].c;
    }
    sort(a + 1, a + m + 1, cmp);
    int s = 0;
    int nrm = 0;
    for(int i = 1; i <= m && nrm < n - 1; i++) {
        int r1 = Find(a[i].x);
        int r2 = Find(a[i].y);
        if(r1 != r2) {
            nrm++;
            sol[nrm] = a[i];
            s += a[i].c;
            Union(a[i].x, a[i].y);
        }
    }
    cout << s << '\n';
    cout << nrm << '\n';
    for(int i = 1; i <= nrm; i++) {
        cout << sol[i].x << ' ' << sol[i].y << '\n';
    }
}