#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 Reuneste (int u, int v) {
    int r1 = culoare[u];
    int r2 = culoare[u];
    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++)
        culoare[i] = i;

    int nrmsol = 0, costFinal = 0;

    for(int i = 0; i < m; i++) {
        if  (culoare[lista[i][0]] != culoare[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;
}