#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>

using namespace std;

const int NMAX = 2 * 1e5 + 1;
const int MMAX = 4 * 1e5 + 1;

struct muchie{
    int x, y, c;
};

muchie e[MMAX];
int t[NMAX], nr[NMAX];

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

int radacina(int x)
{
    if(t[x] == 0)
        return x;
    t[x] = radacina(t[x]);
    return t[x];
}

void reuniune(int x, int y)
{
    int rx = radacina(x);
    int ry = radacina(y);

    if(nr[x] <= nr[y])
    {
        t[rx] = ry;
        nr[ry] += nr[rx];
    }else
    {
        t[ry] = rx;
        nr[rx] += nr[ry];
    }
}

bool interogare(int x, int y)
{
    return (radacina(x) == radacina(y));
}

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

    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        e[i].x = x;
        e[i].y = y;
        e[i].c = c;
    }

    sort(e + 1, e + m + 1, cmp);
    for(int i = 1; i <= n; i++)
        nr[i] = 1;

    bitset <MMAX> viz;

    int cost = 0;
    for(int i = 1; i <= m; i++)
    {
        if(!interogare(e[i].x, e[i].y))
        {
            viz[i] = true;
            cost += e[i].c;
            reuniune(e[i].x, e[i].y);
        }
    }

    fout << cost << "\n" << n - 1 << "\n";
    for(int i = 1; i <= m; i++)
        if(viz[i])
            fout << e[i].x << " " << e[i].y << "\n";

    return 0;
}