#include <fstream>
#include <algorithm>

#define Nmax 200001
#define cost first
#define nodx second.first
#define nody second.second

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

pair < int, pair < int, int > > Muchie[Nmax];
int n, m, tata[Nmax], x, y, c, fx, fy, sum, i, M;

struct {int x, y;} G[Nmax];

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;
        Muchie[i] = {c, {x, y}};
    }
    sort(Muchie + 1, Muchie + m + 1);

    for (i = 1; i <= n; i ++)
        tata[i] = i;

    for (i = 1; i <= m; i ++)
    {
        x = Muchie[i].nodx;
        y = Muchie[i].nody;

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

        if (fx != fy)
        {
            G[++M].y = x;
            G[M].x = y;
            if (fx > fy)
                tata[fx] = fy;
            else
                tata[fy] = fx;

            sum += Muchie[i].cost;
        }
    }
    fout << sum << '\n' << M << '\n';
    for (i = 1; i <= M; i ++)
    {
        fout << G[i].x << " " << G[i].y << '\n';
    }




    fin.close();
    fout.close();
    return 0;
}