#include <fstream>
#include <algorithm>
using namespace std;

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

const int MAXN = 200010, MAXM = 400010;

int N, M, c[MAXN], l, a[MAXN], sum;
// l = nr muchiilor selectate

struct muchie
{
    int st, dr, cost;
} v[MAXM];

inline bool cmp (muchie a, muchie b)
{
    return a.cost < b.cost;
}

int main ()
{
    int i, miin, maax, j;

    fin >> N >> M;
    for (i=1; i<=M; ++i)
        fin >> v[i].st >> v[i].dr >> v[i].cost;
    sort (&v[1], &v[M+1], cmp);

    // indicele componentei conexe din care face parte fiecare nod
    for (i=1; i<=M; ++i)
        c[i] = i;

    for (i=1; i<M; ++i)
    {
        // muchia i nu formeaza cicluri
        if (c[v[i].st] != c[v[i].dr])
        {
            // introduc muchia i in coada
            a[++l] = i;
            sum += v[i].cost;
            // modific indicele componentei conexe pentru toate celelalte noduri din "grupare"
            if (c[v[i].st] < c[v[i].dr])
            {
                miin = c[v[i].st];
                maax = c[v[i].dr];
            }
            else
            {
                miin = c[v[i].dr];
                maax = c[v[i].st];
            }
            for (j=1; j<=N; ++j)
                if (c[j] == maax)
                    c[j] = miin;
        }

    }

    fout << sum << "\n" << l << "\n";
    for (i=1; i<=l; ++i)
    {
        int aux = a[i];
        fout << v[aux].dr << " " << v[aux].st << "\n";
    }


    fin.close();
    fout.close();

    return 0;
}