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

struct muchie
{
    int nod1, nod2, cost;
};

bool cmp(const muchie &m1, const muchie &m2)
{
    return m1.cost < m2.cost;
}

int findr(vector<int> &p, int x)
{
    int root = x;
    while (p[root] != root)
        root = p[root];

    while (x != root) {
        int old = p[x];
        p[x] = root;
        x = old;
    }

    return root;
}

void uniune(vector<int> &p, vector<int> &rang, int x, int y)
{
    x = findr(p, x);
    y = findr(p, y);
    if (x == y)
        return;

    if (rang[x] > rang[y]) {
        p[y] = x;
    }
    else if (rang[y] > rang[x]) {
        p[x] = y;
    }
    else {
        p[y] = x;
        rang[x]++;
    }
}


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

    int n, m;
    fin >> n >> m;

    vector<muchie> muchii(m);
    for (int i = 0; i < m; i++) {
        fin >> muchii[i].nod1 >> muchii[i].nod2
            >> muchii[i].cost;
    }

    sort(muchii.begin(), muchii.end(), cmp);

    vector<int> rang(n+1, 1);
    vector<int> p(n+1);
    for (int i = 1; i <= n; i++)
        p[i] = i;

    int cost_total = 0;
    vector<muchie> folosite;
    //folosite.reserve(muchii.size());

    for (auto m : muchii) {
        int r1 = findr(p, m.nod1);
        int r2 = findr(p, m.nod2);

        if (r1 != r2) {
            uniune(p, rang, r1, r2);
            cost_total += m.cost;
            folosite.push_back(m);
        }
    }

    fout << cost_total << endl;
    fout << folosite.size() << endl;
    for (auto m : folosite)
        fout << m.nod1 << " " << m.nod2 << endl;

    return 0;
}