#include <iostream>
#include <fstream>
#include <algorithm>
#define dMAX 200000

using namespace std;

typedef pair<int, int> pi;
typedef pair<pi, int> ppi;

int n, m, x, y, c, S, cx, cy;
pi arbore[dMAX + 2];
ppi muchii[dMAX * 2 + 2];
bool mu[dMAX * 2 + 2];

ifstream fin("apm.in");
ofstream fout("apm.out");

bool Compare(ppi e1, ppi e2) {
    return e1.second < e2.second;
}

int Find(int k) {
    while (arbore[k].first != 0) {
        k = arbore[k].first;
    }
    return k;
}

void Union(int a, int b) {
    if (arbore[a].second > arbore[b].second) {
        arbore[b].first = a;
    } else arbore[a].first = b;
    if (arbore[a].second == arbore[b].second) arbore[b].second++;
}

int main()
{
    int i, j;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        muchii[i].first = {x, y};
        muchii[i].second = c;
    }
    c = 0;
    sort(muchii + 1, muchii + m + 1, Compare);
    for (i = 1; i <= m; i++) {
        cx = Find(muchii[i].first.first);
        cy = Find(muchii[i].first.second);
        if (cx != cy) {
            S += muchii[i].second;
            mu[i] = true;
            c++;
            Union(cx, cy);
        }
    }
    fout << S << '\n';
    fout << c << '\n';
    for (i = 1; i <= m; i++) {
        if (mu[i]) fout << muchii[i].first.first << ' ' << muchii[i].first.second << '\n';
    }
    return 0;
}