#include <fstream>
#include <iostream>
#include <vector>
#include <queue>


using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");


int n;
int tree[100001];
int rang[100001];

void unite(int x, int y) {
    if (rang[x] >= rang[y]) {
        tree[y] = x;
    } else {
        tree[x] = y;
    }

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

int find(int x) {
    int root, node;

    for (root = x; tree[root] != root; root = tree[root]);

    while (x != root) {
        node = tree[x];
        tree[x] = root;
        x = node;
    }

    return root;
}

struct edge {
    int x;
    int y;
    int c;
};

struct edge_comp {
    bool operator()(const edge &e1, const edge &e2) {
        return e1.c > e2.c;
    }
};

int main() {
    int m;
    int total_cost = 0;

    in >> n >> m;

    priority_queue<edge, vector<edge>, edge_comp> pq;
    vector<edge> ama_edges;

    for (int i = 1; i <= n; ++i) {
        tree[i] = i;
        rang[i] = 0;
    }

    for (int i = 0; i < m; ++i) {
        int x, y, c;

        in >> x >> y >> c;

        edge e = {x, y, c};

        pq.push(e);
    }

    while (n > 1) {
        edge e = pq.top();

        pq.pop();

        if (find(e.x) == find(e.y)) {
            continue;
        }

        --n;

        unite(find(e.x), find(e.y));
        ama_edges.push_back(e);

        total_cost += e.c;
    }

    out << total_cost << '\n';
    out << ama_edges.size() << '\n';

    for (vector<edge>::iterator e = ama_edges.begin(); e != ama_edges.end(); ++e) {
        out << e->x << ' ' << e->y << '\n';
    }

    return 0;
}