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

using namespace std;

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

struct muchie {
    int a, b, c;
    bool operator<(muchie& M) {
        return c < M.c;
    }
};

muchie make_muchie(int a, int b, int c) {
    muchie M;   M.a = a;    M.b = b;    M.c = c;
    return M;
}

vector <muchie> M;
vector <int> grupa(200001);
vector <int> rang(200001, 0);

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

void join(int ra, int rb) {
    if (rang[ra] > rang[rb]) {
        grupa[rb] = ra;
    }
    else {
        if (rang[ra] == rang[rb])
            rang[rb]++;
        grupa[ra] = rb;
    }
}

int main() {
    int n, m;
    int a, b, c;

    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> a >> b >> c;
        M.push_back(make_muchie(a, b, c));
    }
    sort(M.begin(), M.end());

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

    int ra, rb;
    long long int dist = 0;
    vector <muchie> sol;

    for (auto el : M) {
        ra = find_set(el.a);
        rb = find_set(el.b);
        
        if (ra != rb) {
            join(ra, rb);
            dist += el.c;
            sol.push_back(el);
        }
    }

    out << dist << '\n' << sol.size() << '\n';
    for (auto el : sol) {
        out << el.a << ' ' << el.b << '\n';
    }
    
    return 0;
}