#include <bits/stdc++.h>
using namespace std;
using llx = long long;

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

struct much_el
{
    int x, y, c;
    bool operator <(const much_el &alt)
    {
        return c < alt.c;
    }
};

vector<much_el> muchii, much_sol;
vector<int> t, h;

void init(int n)
{
    t.assign(n+1, 0);
    h.assign(n+1, 0);
}

void uneste(int x, int y)
{
    if (h[x] < h[y])
        t[x] = y;
    else
    {
        t[y] = x;
        if (h[x] == h[y])
            h[x]++;
    }
}

int cauta(int x)
{
    int y, r = x;
    while (t[r])
        r = t[r];

    while (x != r)
    {
        y = t[x];
        t[x] = r;
        x = y;
    }
    return r;
}

int main()
{
    int n, m, i, rasp_cost, x, y, c;

    fin >> n >> m;
    init(n);
    for (i = 1; i<=m; i++)
    {
        fin >> x >> y >> c;
        muchii.push_back({x, y, c});
    }

    sort(muchii.begin(), muchii.end());

    rasp_cost = 0;
    for (const auto &much : muchii)
    {
        x = cauta(much.x);
        y = cauta(much.y);
        if (x != y)
        {
            much_sol.push_back(much);
            rasp_cost += much.c;
            uneste(x, y);
        }
    }

    fout << rasp_cost << '\n' << n-1 << '\n';
    for (const auto &much : much_sol)
        fout << much.x << ' ' << much.y << '\n';
    return 0;
}