#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;

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

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

bool operator < (const muchie &x, const muchie &y) {
    return x.cost > y.cost;
}

int n, m, i, f[200001], k=1, contor[200001], sol;
priority_queue<muchie> coada;
vector<int> folos;
vector<muchie> solutie;

void convert(int x, int y) {
    int j;
    for(j = 0; j < folos.size(); j++) {
        if(f[folos[j]] == x) {
            f[folos[j]] = y;
            contor[y]++;
            contor[x]--;
        }
    }
}

int main() {
    fin >> n >> m;
    muchie aux;
    for(i = 0; i < m; i++) {
        fin >> aux.a >> aux.b >> aux.cost;
        coada.push(aux);
    }
    while(!coada.empty()) {
        aux = coada.top();
        coada.pop();
        if((f[aux.a] == 0) && (f[aux.b] == 0)) {
            f[aux.a] = f[aux.b] = k;
            contor[k] += 2;
            k++;
            folos.push_back(aux.a);
            folos.push_back(aux.b);
            sol += aux.cost;
            solutie.push_back(aux);
        }
        else {
            if(f[aux.a] == 0) {
                f[aux.a] = f[aux.b];
                contor[f[aux.b]]++;
                folos.push_back(aux.a);
                sol += aux.cost;
                solutie.push_back(aux);
            }
            else {
                if(f[aux.b] == 0) {
                    f[aux.b] = f[aux.a];
                    contor[f[aux.a]]++;
                    folos.push_back(aux.b);
                    sol += aux.cost;
                    solutie.push_back(aux);
                }
                else {
                    if(f[aux.b] != f[aux.a]) {
                        sol += aux.cost;
                        solutie.push_back(aux);
                        if(contor[f[aux.a]] > contor[f[aux.b]]) {
                            convert(f[aux.b], f[aux.a]);
                        }
                        else {
                            convert(f[aux.a], f[aux.b]);
                        }
                    }
                }
            }
        }
    }
    fout << sol << '\n' << solutie.size() << '\n';
    for(i = 0; i < solutie.size(); i++) {
        fout << solutie[i].a << ' ' << solutie[i].b << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}