#include <cstdio>
#include <algorithm>
#include <bitset>
using namespace std;

const int MMAX = 400003, NMAX = 200003;

bitset <MMAX> is_in_tree;
int edges[NMAX], node1[MMAX], node2[MMAX], cost[MMAX], father[NMAX], max_depth[NMAX], N;

inline bool compare (const int &a, const int &b) {

    return cost[a] < cost[b];

}

struct disjoint_set {

    inline int root (int node) {

        int _root = node, x;
        for (; father[_root] != _root; _root = father[_root]);
        for (; father[node] != _root; node = x)
            x = father[node],
            father[node] = _root;
        return _root;

    }

    inline void unite (const int &root, const int &_root) {

        if (max_depth[root] < max_depth[_root])
            father[root] = _root;
        else
            if (max_depth[root] > max_depth[_root])
                father[_root] = root;
            else
                father[_root] = root,
                ++max_depth[root];

    }

};

disjoint_set E;

int main () {

    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    int M, i, x, y, S = 0, nr = 0;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i)
        scanf ("%d%d%d", node1 + i, node2 + i, cost + i),
        edges[i] = i;
    for (i = 1; i <= N; ++i)
        father[i] = i;
    sort (edges + 1, edges + M + 1, compare);
    for (i = 1; i <= M; ++i) {
        x = E.root (node1[edges[i]]);
        y = E.root (node2[edges[i]]);
        if (x != y)
            is_in_tree[edges[i]] = 1,
            E.unite (x, y),
            S += cost[edges[i]],
            ++nr;
    }
    printf ("%d\n%d\n", S, nr);
    for (i = 1; i <= M; ++i)
        if (is_in_tree[i])
            printf ("%d %d\n", node1[i], node2[i]);

}