#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
long long n, m, x, y, c;
vector <vector <long long>> lista;
vector <long long> culoare;
vector <vector<long long>> raspuns;
bool comp(const vector<long long>& vec1, const vector<long long>& vec2){
    return vec1[2] < vec2[2];
}

void Initilizare(long long u) {
    culoare[u] = u;
}

long long Reprez(long long u) {
    return culoare[u];
}

void Reuneste (long long u, long long v) {
    long long r1 = Reprez(u);
    long long r2 = Reprez(v);
    for (long long k = 1; k <= n; k++)
        if(culoare[k] == r2)
            culoare[k] = r1;
}

int main() {
    f >> n >> m;
    culoare.resize(n + 1);

    for(long long i = 0; i < m; i++) {
        f >> x >> y >> c;
        lista.push_back({x, y, c});
    }

    sort(lista.begin(), lista.end(), comp);

    for(long lonng i = 1; i <= n; i++)
        Initilizare(i);

    int nrmsol = 0, costFinal = 0;

    for(long long i = 0; i < m; i++) {
        if  (Reprez(lista[i][0]) != Reprez(lista[i][1])) {
            costFinal += lista[i][2];
            raspuns.push_back({lista[i][0], lista[i][1]});
            Reuneste(lista[i][0], lista[i][1]);
            nrmsol += 1;
            if(nrmsol == n - 1)
                break;
        }
    }

    g << costFinal << "\n" << raspuns.size() << "\n";

    for(auto it : raspuns) {
        g << it[0] << " " << it[1] << "\n";
    }

    return 0;
}