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

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

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

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

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

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

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

    for(int i = 1; i <= n; i++)
        Initilizare(i);

    int nrmsol = 0, costFinal = 0;

    for(int 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(int i = 0; i < raspuns.size(); i++) {
        g << raspuns[i][0] << " " << raspuns[i][1] << "\n";
    }

    return 0;
}