#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define Nmax 200007
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int N, M, T[Nmax], C[Nmax];
struct el1 {
    int x, y, cost;
};
vector<el1> V;
vector<el1> Ar;

int cmp(el1 x, el1 y) {
    return x.cost < y.cost;
}

void citire() {
    f >> N >> M;
    el1 aux;
    for(int i = 1; i <= M; ++i) {
        f >> aux.x >> aux.y >> aux.cost;
        V.push_back(aux);
    }
    sort(V.begin(), V.end(), cmp);
}

int rad(int i) {
    int localRad = i;
    while(localRad != T[localRad])
        localRad = T[localRad];
    while(T[i] != i) {
        int temp = T[i];
        T[i] = localRad;
        i = temp;
    }
    return localRad;
}

void uneste(int i, int j) {
    if(C[i] >= C[j]) {
        C[i] += j;
        T[j] = i;
        C[j] = 0;
    }
    else {
        C[j] += C[i];
        T[i] = j;
        C[i] = 0;
    }
}

void Krsk() {
    for(int i = 1; i <= N; ++i)
        T[i] = i, C[i] = 1;
    int r1, r2, S = 0, nr = 0, it = 0;
    while(nr != N - 1) {
        el1 aux = V[it];
        r1 = rad(aux.x);
        r2 = rad(aux.y);
        if(r1 != r2) {
            //unesc
            uneste(r1, r2);
            Ar.push_back(aux);
            S += aux.cost;
            nr++;
        }
        it++;
    }
    g << S << '\n';
    g << N - 1 << '\n';
    for(int i = 0; i < N - 1; ++i)
        g << Ar[i].x << " " << Ar[i].y << '\n';
}

int main() {
    citire();
    Krsk();
    return 0;
}