#include <cstdio>
#include <algorithm>
#include <vector>
#define n1 second.first
#define n2 second.second
using namespace std;

class disjoint_set {

    int *dj, *max_depth;

    public:

    disjoint_set (const int &size) {
        dj = new int[size + 1];
        max_depth = new int[size + 1];
        for (int i = 1; i <= size; ++i)
            dj[i] = max_depth[i] = 0;
    }

    inline void unite (const int &node1, const int &node2) {

        if (max_depth[node1] < max_depth[node2])
            dj[node1] = node2;
        else
        if (max_depth[node1] > max_depth[node2])
            dj[node2] = node1;
        else {
            dj[node2] = node1;
            ++max_depth[node1];
        }

    }

    int root (int node) {

        int aux = node, _aux;
        while (dj[node]) {
            node = dj[node];
        }
        while (dj[aux]) {
            _aux = aux;
            aux = dj[aux];
            dj[_aux] = node;
        }
        return node;
    }

};

const int NMAX = 200003;

vector <pair <int, pair <int, int> > > edges;
vector <pair <int, int> > ans;
disjoint_set DJ(NMAX);

int main () {

    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    int N, M, i, a, b, c, cost = 0;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i) {
        scanf ("%d%d%d", &a, &b, &c);
        edges.push_back (make_pair (c, make_pair (a, b)));
    }
    sort (edges.begin (), edges.end ());
    for (vector <pair <int, pair <int, int> > > :: iterator k = edges.begin (); k != edges.end (); ++k) {
        int o = DJ.root (k->n1),
            p = DJ.root (k->n2);
        if (o != p) {
            DJ.unite (o, p);
            cost += k->first;
            ans.push_back (make_pair (k->n1, k->n2));
        }
    }
    printf ("%d\n%d\n", cost, N - 1);
    for (vector <pair <int, int> > :: iterator k = ans.begin (); k != ans.end (); ++k)
        printf ("%d %d\n", k->first, k->second);

}