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

const int NMAX = 200003, MMAX = 400003;

struct edge {

    int t, not_t, cost;
    bool operator < (const edge &a) {
        return cost < a.cost;
    }

};

class heap {

    edge E[MMAX];
    int size;
    inline int _min (const int &a, const int &b) {

        return E[a] < E[b] ? a : b;

    }
    inline void sift (int x) {

        int k;
        edge e = E[x];
        for (; x * 2 <= size; x = k) {
            if (x * 2 + 1 <= size)
                k = _min (x * 2, x * 2 + 1);
            else
                k = x * 2;
            if (E[k] < E[x]) {
                E[x] = E[k];
                E[k] = e;
            }
            else
                break;
        }
        E[x] = e;

    }
    inline void percolate (int x) {

        edge k = E[x];
        for (; x != 1 && E[x] < E[x / 2]; x /= 2) {
            E[x] = E[x / 2];
            E[x / 2] = k;
        }
    }
public:
    inline void push (const edge &k) {

        E[++size] = k;
        percolate (size);

    }
    inline void pop () {

        E[1] = E[size--];
        sift (1);

    }
    inline edge top () {

        return E[1];

    }
    inline bool empty () {

        return !size;

    }

};

inline edge make_edge (const int &t, const int &not_t, const int &cost) {

    edge a;
    a.t = t;
    a.not_t = not_t;
    a.cost = cost;
    return a;

}

vector <pair <int, int> > G[NMAX], R;
bitset <NMAX> in_tree;
heap H;

int main () {

    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    vector <pair <int, int> > :: iterator j;
    edge k;
    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) {
        H.push (make_edge (1, j->node, j->cost));
    }
    in_tree[1] = 1;
    while (!H.empty ()) {
        k = H.top ();
        H.pop ();
        if (in_tree[k.not_t])
            continue;
        R.push_back (make_pair (k.t, k.not_t));
        _R += k.cost;
        in_tree[k.not_t] = 1;
        for (j = G[k.not_t].begin (); j != G[k.not_t].end (); ++j)
            if (!in_tree[j->node])
                H.push (make_edge (k.not_t, j->node, j->cost));
    }
    printf ("%d\n%d", _R, R.size ());
    for (j = R.begin (); j != R.end (); ++j)
        printf ("\n%d %d", j->node, j->cost);

}