#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, m, sol = 0;
vector <int> x, y, c, a, s, v;
// x y c - caracteristecele muchii (din x[i] exista muchie in y[i] cu costul c[i])
// s - indecele x, y si c sortate
// a - pentru a verifica daca muchiile folosite nu formeaza ciclu
// v - muchiile folosite

bool compare(int i, int j)
{
    return c[i] < c[j];
}

int f(int i)
{
    if (a[i] == i) return i;
    a[i] = f(a[i]);
    return a[i];
}

void read()
{
    fin >> n >> m;
    x.resize(m);
    y.resize(m);
    c.resize(m);
    s.resize(m);
    a.resize(n + 1);

    for (int i = 0; i < a.size(); i++) a[i] = i;
    for (int i = 0; i < x.size(); i++)
    {
        s[i] = i;
        fin >> x[i] >> y[i] >> c[i];
    }
}

void solve()
{
    sort(s.begin(), s.end(), compare);

    for (int i = 0; i < x.size(); i++)
        if (f(x[ s[i] ]) != f(y[ s[i] ]))
        {
            sol += c[ s[i] ];
            a[f( x[ s[i] ] )] = f( y[ s[i] ] );
            v.push_back(s[i]);
        }
}

void write()
{
    cout << sol << '\n' << v.size() << '\n';
    for (int q, i = 0; i < v.size(); i++)
    {
        q = v[i];
        cout << x[q] << ' ' << y[q] << '\n';
    }
}

int main()
{
	read();

	solve();

	write();

	return 0;
}