#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int n, m, cost_total = 0;
vector<pair<int, pair<int, int>>> muchii;
vector<pair<int, int>> apcm;
vector<int> tt, r;

int Find(int nod)
{
    while (tt[nod] != 0)
        nod = tt[nod];
    return nod;
}

void Union(int x, int y) {
    int tt_x = Find(x);
    int tt_y = Find(y);
    if(r[tt_x] > r[tt_y]) {
        tt[tt_y] = tt_x;
    } else {
        tt[tt_x] = tt_y;
        if(r[tt_x] == r[tt_y]) {
            r[tt_y]++;
        }
    }
}

void Afisare() {
    cout << cost_total << '\n';
    cout << apcm.size() << '\n';
    for (const auto &muchie : apcm)
    {
        cout << muchie.first << ' ' << muchie.second << '\n';
    }
}

int main()
{
    cin >> n >> m;
    muchii.assign(m, {0, {0, 0}});
    tt.assign(n + 1, 0);
    r.assign(n + 1, 0);
    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        muchii[i] = {c, {x, y}};
    }
    sort(muchii.begin(), muchii.end());
    for (const auto &muchie : muchii)
    {
        int cost = muchie.first, x = muchie.second.first, y = muchie.second.second;
        if (Find(x) != Find(y))
        {
            Union(x, y);
            apcm.push_back({x, y});
            cost_total += cost;
            if (apcm.size() == n - 1)
            {
                break;
            }
        }
    }
    Afisare();
    return 0;
}