#include <fstream>
#include <algorithm>

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

const int NMAX = 200001;
const int MMAX = 400001;

int n, m, arb[NMAX], k;
long long c;

struct muchie
{
    int x, y, cost;
} v[MMAX], a[NMAX];

bool comparare(muchie e, muchie ee)
{
    return e.cost < ee.cost;
}

int find_root(int nod)
{
    if (arb[nod] == nod)
        return nod;
    return arb[nod] = find_root(arb[nod]);
}

void Kruskal()
{
    int root_x, root_y;
    for (int i = 1; i <= n; i++)
        arb[i] = i;

    for (int i = 1; i <= m && k < n - 1; i++)
    {
        root_x = find_root(v[i].x);
        root_y = find_root(v[i].y);

        if (root_x != root_y)
        {
            c = c + v[i].cost;
            a[++k] = v[i];
            arb[root_x] = root_y;
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;

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

    Kruskal();

    fout << c << '\n';
    fout << k << '\n';
    for (int i = 1; i <= k; i++)
        fout << a[i].x << " " << a[i].y << '\n';

    return 0;
}