#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct muchie {
    int a, b, c;

    muchie(int A, int B, int C) {
        a = A;
        b = B;
        c = C;
    }
    bool operator<(muchie A) {
        return c < A.c;
    }
};

vector <muchie> M;
vector <int> grupa(200001);

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

int find_set(int nod) {
    if (nod == grupa[nod])
        return nod;
    grupa[nod] = find_set(grupa[nod]);
    return grupa[nod];
}

void joint(int a, int b) {
    grupa[a] = b;
}

int main() {
    int n, m;
    in >> n >> m;
    
    int a, b, c;
    for (int i = 0; i < m; i++) {
        in >> a >> b >> c;
        muchie MUCHIE(a, b, c);
        M.push_back(MUCHIE);
    }

    sort(M.begin(), M.end());

    for (int i = 1; i <= n; i++)
        grupa[i] = i;

    long long int cost = 0;
    vector <muchie> sol;

    for (auto element : M) {
        if (find_set(element.a) != find_set(element.b)) {
            cost += element.c;
            joint(find_set(element.a), find_set(element.b));
            sol.push_back(element);
        }
    }
    
    out << cost << '\n' << sol.size() << '\n';
    for (auto element : sol) {
        out << element.a << ' ' << element.b << '\n';
    }

    return 0;
}