#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

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

struct muchie
{
    int n1, n2, cost;
};

muchie x[1000000], afis[10000];
int t[10000], rang[10000];

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

int multime(int n)
{
    if (t[n] != n)
    {
        t[n] = multime(t[n]);
    }
    return t[n];
}

void unire(int t1, int t2)
{
    if (rang[t1] > rang[t2])
    {
        t[t1] = t2;
    }
    else
    {
        if (rang[t1] < rang[t2])
        {
            t[t2] = t1;
        }
        else
        {
            if (rang[t1] == rang[t2])
            {
                rang[t1]++;
                t[t1] = t2;
            }
        }
    }
}

int main()
{
    int n, m, tatal1, tatal2, c = 0, s = 0, z = 0;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> x[i].n1 >> x[i].n2 >> x[i].cost;
    }
    sort(x + 1, x + m + 1, criteriu);
    for (int i = 1; i <= n; i++)
        t[i] = i;
    for (int i = 1; i <= m && c <= n - 1; i++)
    {
        tatal1 = multime(x[i].n1);
        tatal2 = multime(x[i].n2);
        if (tatal1 != tatal2)
        {
            unire(tatal1, tatal2);
            s = s + x[i].cost;
            afis[++z].n1 = x[i].n1;
            afis[z].n2 = x[i].n2;
            c++;
        }
    }
    g << s << "\n" << c << "\n";
    for (int i = 1; i <= z; i++)
        g << afis[i].n1 << " " << afis[i].n2 << "\n";
    return 0;
}