#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 (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) {
        int p1 = find(e[i].nod1, parent);
        int p2 = find(e[i].nod2, parent);

        if (p1 != p2) {
            folosit[i] = true;
            cost += e[i].cost;

            uniune(p1, p2, parent, rang);
        }
    }

    fout << cost << "\n";
    fout << n-1 << "\n";

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

    return 0;
}