#include <iostream>
#include <set>
#include <fstream>
#include <vector>

using namespace std;

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

const int maxN = 2e5 + 5;

int rang[maxN], t[maxN];
set <pair<int,pair<int,int>>> muchii;
vector <pair<int,int>> apm;

int radacina (int node) {
    if(t[node] == 0)
        return node;

    int root = radacina(t[node]);
    t[node] = root;
    return root;
}

signed main()
{
    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int u, v, c;
        fin >> u >> v >> c;

        muchii.insert({c, {u, v}});
    }

    int apmCost = 0;
    for(auto edge : muchii) {
        int u = edge.second.first;
        int v = edge.second.second;
        int c = edge.first;

        int rad1 = radacina(u), rad2 = radacina(v);

        if(rad1 != rad2) {

            apmCost += c;
            apm.push_back({u, v});

            if(rang[rad1] > rang[rad2]) {
                t[rad2] = rad1;
            } else {
                t[rad1] = rad2;
                if(rang[rad1] == rang[rad2])
                    rang[rad1]++;
            }
        }
    }

    fout << apmCost << '\n';
    fout << apm.size() << '\n';

    for(auto edge : apm)
        fout << edge.first << " " << edge.second << '\n';

    return 0;
}