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

using namespace std;

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

int n, m, poz;

struct muchie
{
    int x, y, c;
};
int viz[200005], rankk[200005], cost;
muchie v[400006], aux, finally[400006];

void citire()
{
    f >> n >> m;

    for (int i = 1; i <= m; i++)
        f >> v[i].x >> v[i].y >> v[i].c;
}

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

int findd(int i)
{
    while (viz[i] != i)
        i = viz[i];
    return i;
}

void unionn(int m1, int m2)
{
    if (rankk[m1] < rankk[m2])
        viz[m1] = m2;
    if (rankk[m1] > rankk[m2])
        viz[m2] = m1;
    if (rankk[m1] == rankk[m2])
    {
        viz[m1] = m2;
        rankk[m2]++;
    }
}
void afisare()
{
    g << cost << "\n" << n - 1 << "\n";
    for (int i = 1; i <= n - 1; i++)
        g << finally[i].y << " " << finally[i].x << "\n";
}
int main()
{
    citire();
    sort(v + 1, v + m + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        viz[i] = i; rankk[i] = 1;
    }
    for (int i = 1; i<= m; i++)
    {
        int m1 = findd(v[i].x);
        int m2 = findd(v[i].y);
        if (m1 != m2)
        {
            poz++;
            unionn(m1, m2);
            finally[poz].x = v[i].x;
            finally[poz].y = v[i].y;
            cost += v[i].c;
        }


    }
    afisare();

    return 0;
}