#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
int n, m, i, x, cost, y, k;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x, y, k;
};
vector <muchie> v, sol;
vector <int> t, p;
int root (int k)
{
    while (k != t[k])
        k = t[k];
    return k;
}
void unificare (int x, int y)
{
    if (p[x] < p[y])
        t[x] = y;
    if (p[x] > p[y])
        t[y] = x;
    if (p[x] == p[y])
    {
        t[y] = x;
        p[x]++;
    }
}
bool comp (muchie a, muchie b)
{
    return a.k < b.k;
}
int main()
{
    fin >> n >> m; v.resize(m+1); t.resize(m+1); p.resize(n+1); sol.resize(n);
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> k;
        v[i].x = x; v[i].y = y; v[i].k = k;
        t[i] = i;
    }
    sort (v.begin()+1, v.end(), comp);
    i = 1; k = 0;
    while (k < n-1)
    {
        int rx = root(v[i].x), ry = root(v[i].y);
        if (rx != ry)
        {
            ++k;
            cost += v[i].k;
            sol[k] = v[i];
            unificare (rx, ry);
        }
        i++;
    }
    fout << cost << "\n" << n-1 << '\n';
    for (i = 1; i <= n-1; i++)
        fout << sol[i].y << " " << sol[i].x << '\n';
    return 0;
}