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

vector < pair < int, int > > g[nmax];
int n, m, c, i, x, y, tata[nmax], cm, fx, fy;
pair < int, pair < int, int > > mu[400001];
vector < pair < int, int > > sol;

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

    return tata[x] = f (tata[x]);
}

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

    sort (mu + 1, mu + m  +1);

    for (i = 1; i <= m; i++)
    {
        x = mu[i].second.first;
        y = mu[i].second.second;

        fx = f (x);
        fy = f (y);

        if (fx != f (y))
        {
            sol.push_back (make_pair (x, y));
            if (fx > fy) tata[fx] = fy;
            else
                tata[fy] = fx;
            cm += mu[i].first;
        }
    }

    fout << cm << "\n" << sol.size () << '\n';
    for (i = 0; i < sol.size (); i++)
        fout << sol[i].first << " " << sol[i].second << '\n';

    return 0;
}