#include <bits/stdc++.h>

using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

const int nmax = 2e5 + 3;

struct usor
{
    int a, b, c;
}v[nmax];

int usu[nmax], n, m, sol, afis[nmax], nr;

bool cmp(usor a, usor b)
{
    return a.c < b.c;
}

int gr(int nod)
{
    if (usu[nod] == nod)
        return nod;
    usu[nod] = gr(usu[nod]);
    return usu[nod];
}

void unite(int a, int b)
{
    usu[gr(a)] = gr(b);
}

int main()
{
    f >> n >> m;

    for (int i = 1; i <= m; ++i)
        f >> v[i].a >> v[i].b >> v[i].c;

    sort(v + 1, v + m + 1, cmp);

    for (int i = 1; i <= n; ++i)
        usu[i] = i;

    for (int i = 1; i <= m; ++i)
    {
        if (gr(v[i].a) != gr(v[i].b))
        {
            sol += v[i].c;
            unite(v[i].a, v[i].b);
            afis[++nr] = i;
        }
    }

    g << sol << '\n' << n - 1 << '\n';

    for (int i = 1; i < n; ++i)
        g << v[afis[i]].a << ' ' << v[afis[i]].b << '\n';

    return 0;
}