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

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

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

int find(int n, vector<int> &parent)
{
    int p = n;

    while (parent[p] != p) {
        p = parent[p];
    }

    while (parent[n] != p) {
        int urm = parent[n];
        parent[n] = p;
        n = urm;
    }

    return p;
}

void uniune(int n1, int n2, vector<int> &parent, vector<int> &rang) {
    n1 = find(n1, parent);
    n2 = find(n2, parent);

    if (rang[n1] > rang[n2]) {
        parent[n2] = n1;
    }
    else if (rang[n1] < rang[n2]) {
        parent[n1] = n2;
    }
    else {
        parent[n2] = n1;
        rang[n1]++;
    }
}


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

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

    vector<Muchie> e(m);

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

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

    vector<bool> folosit(m, false);
    int cost = 0;

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

    for (int i = 0; i < m; ++i) {
        if (find(e[i].nod1, parent) != find(e[i].nod2, parent)) {
            folosit[i] = true;
            cost += e[i].cost;

            uniune(e[i].nod1, e[i].nod2, parent, rang);
        }
    }

    fout << cost << endl;
    fout << n-1 << endl;

    for (int i = 0; i < m; ++i) {
        if (folosit[i]) {
            fout << e[i].nod1 << ' ' << e[i].nod2 << endl;
        }
    }

    return 0;
}