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

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

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

muchie x[100000], afis[10000];
int t[2000];

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

int main()
{
    int n, m, 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; i++)
    {
        if (t[x[i].n1] != t[x[i].n2])
        {
            s = s + x[i].cost;
            afis[++z].n1 = x[i].n1;
            afis[z].n2 = x[i].n2;
            int t1, t2;
            t1 = t[x[i].n1];
            t2 = t[x[i].n2];
            for (int j = 1; j <= n; j++)
            {
                if (t[j] == t1)
                    t[j] = t2;
            }
        }
    }
    g << s << "\n" << z << "\n";
    for (int i = 1; i <= z; i++)
    {
        g << afis[i].n1 << " " << afis[i].n2 << "\n";
    }
    return 0;
}