#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, rnk[200001], p[200001], cost;

struct muchie {
    int a, b;
    int c;
};

bool operator < (muchie x, muchie y) {
    return x.c > y.c;
}

vector<muchie> solutie;
priority_queue<muchie> q;

void citire() {
    fin >> n >> m;
    muchie x;
    for(int i = 1; i <= m; i++) {
        fin >> x.a >> x.b >> x.c;
        q.push(x);
    }
}

int parinte(int nod) {
    if(p[nod] == 0)
        return nod;
    p[nod] = parinte(p[nod]);
    return p[nod];
}

void kruskal() {
    while(!q.empty()) {
        muchie crt = q.top();
        q.pop();
        int aa, bb;
        aa = parinte(crt.a);
        bb = parinte(crt.b);
        if(aa != bb) {
            if(rnk[aa] < rnk[bb]) {
                swap(aa, bb);
            }
            p[bb] = aa;
            solutie.push_back(crt);
            rnk[aa] += rnk[bb] + 1;
            cost += crt.c;
        }
    }
}

int main() {
    citire();
    kruskal();
    fout << cost << "\n" << n-1 << "\n";
    for(int i = 0; i < n - 1; i++) {
        fout << solutie[i].a << " " << solutie[i].b << "\n";
    }
    return 0;
}