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

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

const int MAXM = 410000;
const int MAXN = 210000;

typedef std::pair <int, std::pair <int, int> > muchie;

int N, M;
muchie v[MAXM];

int arb[MAXN], na[MAXN];
std::vector <pair <int, int> > solutie;

int dad (int a) {
    if (arb[a] == a) return a;

    arb[a] = dad(arb[a]);

    return arb[a];
}

void uneste (int a, int b) {
    int da = dad(a);
    int db = dad(b);

    if (na[da] > na[db])
        arb[db] = da;
    else if(na[da] < na[db])
        arb[da] = db;
    else {
        arb[db] = da;
        ++na[da];
    }
}

int main() {
    fin >> N >> M;

    for (int i = 1; i <= M; ++i)
        fin >> v[i].second.first >> v[i].second.second >> v[i].first;

    std::sort (v + 1, v + M + 1);

    for (int i = 1; i <= N; ++i)
        arb[i] = i;

    int cost = 0;

    for (int i = 1; i <= M; ++i) {
        int x = v[i].second.first;
        int y = v[i].second.second;

        if (dad(x) != dad(y)) {
            uneste(x, y);
            cost += v[i].first;
            solutie.push_back(make_pair(x, y));
        }
    }

    fout << cost << "\n" << solutie.size() << "\n";

    for (int i = 0; i < solutie.size(); ++i)
        fout << solutie[i].first << " " << solutie[i].second << "\n";

    return 0;
}