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

struct ura
{
    int x, y, c;
} v[400001];
struct solutie
{
    int x, y;
} sol[200000];
int sef[200001];

bool cmp(ura a, ura b)
{
    if (a.c < b.c)
        return true;
    else
        return false;
}

int s(int nod)
{
    if (sef[nod] == nod)
        return nod;
    else
        return sef[nod] = s(sef[nod]);
}

void u(int x, int y)
{
    int sefx = s(x), sefy = s(y);
    sef[sefy] = sefx;
}

int main()
{
    int n, m, i, cm = 0, nrm = 0;
    in >> n >> m;
    for (i = 1; i <= m; i++)
        in >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + m + 1, cmp);
    for (i = 1; i <= n; i++)
        sef[i] = i;
    for (i = 1; i <= m && nrm <= n - 2; i++)
    {
        int sefx = s(v[i].x), sefy = s(v[i].y);
        if (sefx != sefy)
        {
            u(v[i].x, v[i].y);
            cm += v[i].c;
            nrm++;
            sol[nrm].x = v[i].x;
            sol[nrm].y = v[i].y;
        }
    }
    out << cm << "\n";
    out << nrm << "\n";
    for (i = 1; i <= nrm; i++)
        out << sol[i].x << " " << sol[i].y << "\n";
    return 0;
}