#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)
{
    while (parent[n] != n) {
        n = parent[n];
    }

    return n;
}

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

    parent[n2] = 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);
    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);
        }
    }

    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;
}