#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 200001;
const int MMAX = 400001;

int n, m;           
int arb[NMAX];
int k;                  
long long c;              

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

muchie v[MMAX];
muchie a[NMAX]; 

bool comparare(muchie e1, muchie e2) {
    return e1.cost < e2.cost;
}

int find_root(int nod) {
    if (arb[nod] == nod) {
        return nod;
    }
    return arb[nod] = find_root(arb[nod]);
}

void Kruskal() {
    int rootx, rooty;

    for (int i = 1; i <= n; i++) {
        arb[i] = i;
    }

    for (int i = 1; i <= m && k < n - 1; i++) {
        rootx = find_root(v[i].x);
        rooty = find_root(v[i].y);

        if (rootx != rooty) {
            c = c + v[i].cost;
            a[++k] = v[i];
            arb[rootx] = rooty;
        }
    }
}

int main() {
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }

    sort(v + 1, v + m + 1, comparare);

    Kruskal();
    fout << c << '\n';
    fout << k << '\n';
    for (int i = 1; i <= k; i++) {
        fout << a[i].x << " " << a[i].y << '\n';
    }

    return 0;
}