#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

#define lim 200010
struct nod{int x, y, c;} g[2*lim];
int d[lim];
struct ssol{int x, y;} sol[2*lim];

bool cmp (nod a, nod b)
{
    if (a.c < b.c)  return 1;
    return 0;
}


int get_dad (int x)
{
    if (x != d[x]) d[x] = get_dad(d[x]);
    return d[x];
}


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

    sort(g+1, g+m+1, cmp);
    for (int i=1; i <= n; i++)  d[i] = i;

    int rez = 0, k = 0;
    for (int i=1; i <= m; i++)
        if ( get_dad(g[i].x) != get_dad(g[i].y) )
        {
            d[get_dad(g[i].x)] = get_dad(g[i].y);
            rez += g[i].c;
            sol[++k].x = g[i].x;
            sol[k].y = g[i].y;
        }

    fout << rez << '\n';
    fout << k << '\n';
    for (int i=1; i <= k; i++)
        fout << sol[i].x << ' ' << sol[i].y << '\n';

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