#include <fstream>
#include <algorithm>
using namespace std;

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

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

muchie v[400002];
int n, m, nr_muchii = 0, cost_final = 0;
int parinte[200002], marime[200002], viz[400002];
int i;

bool comparare(muchie a, muchie b)
{
    return (a.cost < b.cost);
}

int parinte_suprem(int x)
{
    int x_copie = x;
    while (x_copie != parinte[x_copie])
    {
        x_copie = parinte[x_copie];
    }

    int x_copie2 = x;
    while (x_copie2 != parinte[x_copie2])
    {
        x_copie2 = parinte[x_copie2];
        parinte[x_copie2] = x_copie;
    }

    return x_copie;
}

void unire(int x, int y)
{
    int x_copie = x;
    while (x_copie != parinte[x_copie])
    {
        x_copie = parinte[x_copie];
    }

    int x_copie2 = x;
    while (x_copie2 != parinte[x_copie2])
    {
        x_copie2 = parinte[x_copie2];
        parinte[x_copie2] = x_copie;
    }

    int  y_copie = y;
    while (y_copie != parinte[y_copie])
    {
        y_copie = parinte[y_copie];
    }

    int y_copie2 = y;
    while (y_copie2 != parinte[y_copie2])
    {
        y_copie2 = parinte[y_copie2];
        parinte[y_copie2] = y_copie;
    }

    if (marime[x_copie] >= marime[y_copie])
    {
        parinte[y_copie] = x_copie;
        marime[x_copie] += marime[y_copie];
    }
    else
    {
        parinte[x_copie] = y_copie;
        marime[y_copie] += marime[x_copie];
    }

    nr_muchii++;
}

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

    for (i = 1; i <= n; i++)
    {
        parinte[i] = i;
        marime[i] = 1;
    }

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

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

    unire(v[1].x, v[1].y);
    cost_final += v[1].cost;
    viz[1] = 1;

    unire(v[2].x, v[2].y);
    cost_final += v[2].cost;
    viz[2] = 1;

    for (i = 3; i <= m; i++)
    {
        if (parinte_suprem(v[i].x) != parinte_suprem(v[i].y))
        {
            unire(v[i].x, v[i].y);
            cost_final += v[i].cost;
            viz[i] = 1;
        }
    }

    fout << cost_final << "\n" << nr_muchii << "\n";

    for (i = 1; i <= m; i++)
        if (viz[i])
        {
            fout << v[i].x << " " << v[i].y << "\n";
        }
    return 0;
}