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

const int NMAX = 200003;

vector <pair <int, int> > R;
vector <int> G[NMAX];
pair <int, pair <int, int> > E[NMAX];
int dj_set[NMAX], depth_max[NMAX];

inline int djset_root (const int &n) {

    int k = n, p = n, a;
    while (dj_set[k]) {
        k = dj_set[k];
    }
    while (dj_set[p]) {
        a = dj_set[p];
        dj_set[p] = k;
        p = a;
    }
    return k;

}

void djset_unite (const int &n, const int &_n) {

    if (depth_max[n] > depth_max[_n])
        dj_set[_n] = n;
    else
        if (depth_max[n] < depth_max[_n])
            dj_set[n] = _n;
        else {
            dj_set[n] = _n;
            ++depth_max[_n];
        }

}

int main () {

    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    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);
        E[i] = make_pair (c, make_pair (a, b));
    }
    sort (E + 1, E + M + 1);
    for (i = 1; i <= M; ++i) {
        a = djset_root (E[i].node);
        b = djset_root (E[i]._node);
        if (a != b) {
            _R += E[i].cost;
            R.push_back (E[i].second);
            djset_unite (a, b);
        }
    }
    printf ("%d\n%d", _R, R.size ());
    for (vector <pair <int, int> > :: iterator j = R.begin (); j != R.end (); ++j)
        printf ("\n%d %d", j->first, j->second);

}