#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
#define node first
#define cost second
using namespace std;

const int NMAX = 200002;

struct edge {

    int node, _node, cost;

};

inline edge make_edge (const int &node, const int &_node, const int &cost) {

    edge t;
    t.node = node;
    t._node = _node;
    t.cost = cost;
    return t;

}

struct compare {

    inline bool operator () (const edge &a, const edge &b) {

        return a.cost > b.cost;

    }

};

vector <pair <int, int> > G[NMAX], R;
priority_queue <edge, vector <edge>, compare> Q;
bitset <NMAX> in_tree;

int main () {

    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    vector <pair <int, int> > :: iterator j;
    edge e;
    int N, M, i, a, b, c, _R = 0;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i) {
        scanf ("%d%d%d", &a, &b, &c);
        G[a].push_back (make_pair (b, c));
        G[b].push_back (make_pair (a, c));
    }
    for (j = G[1].begin (); j != G[1].end (); ++j)
        Q.push (make_edge (1, j->node, j->cost));
    in_tree[1] = 1;
    while (!Q.empty ()) {
        e = Q.top ();
        Q.pop ();
        if (in_tree[e._node])
            continue;
        _R += e.cost;
        R.push_back (make_pair (e.node, e._node));
        in_tree[e._node] = 1;
        for (j = G[e._node].begin (); j != G[e._node].end (); ++j)
            if (!in_tree[j->node])
                Q.push (make_edge (e._node, j->node, j->cost));
    }
    printf ("%d\n%d\n", _R, R.size ());
    for (j = R.begin (); j != R.end (); ++j)
        printf ("%d %d\n", j->node, j->cost);

}