#include <fstream>
#define nmax 200001
#define cost first
#define nod second
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

pair < int, pair < int, int > > mu[nmax];
struct cel {int first, second;}; cel sol[nmax];
int i, j, c, tata[nmax], cm, n, m, x, y, fx, fy, nr;

int f (int x)
{
    if (tata[x] == x)
        return x;
    return tata[x] = f(tata[x]);
}

int main()
{
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {   fin >> x >> y >> c;
        mu[i] = make_pair (c, make_pair (x, y));
    }
    sort (mu + 1, mu + 1 + m);
    for (i = 1; i <= n; i++)
        tata[i] = i;

    for (i = 1; i <= m; i++)
    {
        x = mu[i].second.first;
        y = mu[i].second.second;
        fx = f (x);
        fy = f (y);
        if (fx != fy)
        {
            sol[++nr].second = x;
            sol[nr].first = y;
            if (fx > fy)
            {
                tata[fx] = fy;
            }
            else
                tata[fy] = fx;

            cm += mu[i].first;
        }
    }

    fout << cm << "\n" << nr << "\n";
    for (int i = 1; i <= nr; i++)
        fout << sol[i].first << " " << sol[i].second << "\n";

    return 0;
}