//complexitate : O(m log m)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<pair<int, int>,
            int> > graph;

class DsjDataSet {
    vector<int> rang;
    vector<int> parent;
public:
    DsjDataSet(int);
    ~DsjDataSet();
    int findRoot(int);
    void link(int, int);
    void unionSets(int, int);
};

DsjDataSet::DsjDataSet(int n) {
    rang.resize(n + 1, 0);
    parent.resize(n + 1);
    for (int i = 0; i < n + 1; i++) {
        parent[i] = i;
    }
}

DsjDataSet::~DsjDataSet() {
}

int DsjDataSet::findRoot(int x) {
    int i;

    for (i = x; parent[i] != i; i = parent[i]) {
    }

    // i is the root
    int aux;
    while (parent[x] != x) {  // path compression
        aux = parent[x];
        parent[x] = i;
        x = aux;
        rang[i]--;
    }
    return i;
}

void DsjDataSet::link(int x, int y) {
    if (rang[x] < rang[y]) {        // reuniunea dupa rang
        parent[x] = y;
    } else {
        if (rang[x] > rang[y]) {
            parent[y] = x;
        } else {
            parent[x] = y;
            rang[y]++;
        }
    }
}

void DsjDataSet::unionSets(int x, int y) {
    link(findRoot(x), findRoot(y));
}

bool cmp(const pair<pair<int, int>, int>& a,
         const pair<pair<int, int>, int>& b) {
    if (a.second < b.second) {
        return true;
    }
    return false;
}

vector<pair<int, int> > getAPM(vector<pair<pair<int, int>, int> > graph, int n, int &costTot) {
    sort(graph.begin(), graph.end(), cmp);

    DsjDataSet DDS(n);
    vector<pair<int, int> > APMedges;
    int x, y, cost;
    for (int i = 0; i < graph.size(); i++) {
        x = graph[i].first.first;
        y = graph[i].first.second;
        cost = graph[i].second;

        if (DDS.findRoot(x) != DDS.findRoot(y)) {
            APMedges.push_back(make_pair(x, y));
            DDS.unionSets(x, y);
            costTot += cost;
        }
    }

    return APMedges;
}

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;

    f >> n >> m;

    int x, y, cost;
    for (int i = 0; i < m; i++) {
        f >> x >> y >> cost;
        graph.push_back(make_pair(make_pair(x, y), cost));
    }

    int costTot = 0;
    vector<pair<int, int> > edgesApm = getAPM(graph, n, costTot);

    g << costTot << endl;
    g << edgesApm.size() << endl;

    for (auto it = edgesApm.begin(); it != edgesApm.end(); it++) {
        g << it->first << " " << it->second << "\n";
    }

    f.close();
    g.close();

    return 0;
}