#include <iostream>
#include <fstream>

#define pinf 50001

using namespace std;

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

struct muchie{
    int x, y, cost;
};

int i, j, c, k, n, m, viz[200010], ans, rasp1[200010], rasp2[200010];
muchie v[200010], aux;

void kruskal()
{
    int i, a, b, j, minn, z=1, maxx;
    for(i=1; i<=n; i++)
    {
        viz[i] = i;
    }
    i=1;
    while( z<=n-1 )
    {
        if( viz[ v[i].x ] != viz[ v[i].y ] )
        {
            rasp1[z] = v[i].x;
            rasp2[z] = v[i].y;
            ans += v[i].cost;
            z++;
        }
        if( viz[ v[i].x ] < viz[ v[i].y ] )
        {
            minn = viz[ v[i].x ];
            maxx = viz[ v[i].y ];
        }
        else
        {
            minn = viz[ v[i].y ];
            maxx = viz[ v[i].x ];
        }
        for(j=1; j<=n; j++)
        {
            if( viz[j] == maxx )
            {
                viz[j] = minn;
            }
        }
        i++;
    }
}

int main()
{
    fin >> n >> m;
    for(k=1; k<=m; k++)
    {
        fin >> i >> j >> c;
        v[k].x = i;
        v[k].y = j;
        v[k].cost = c;
    }
    for(i=1; i<=m; i++)
    {
        for(j=1; j<=m; j++)
        {
            if( v[i].cost < v[j].cost )
            {
                aux = v[i];
                v[i] = v[j];
                v[j] = aux;
            }
        }
    }
    kruskal();
    fout << ans << '\n';
    fout << n-1 << '\n';
    for(i=1; i<=n-1; i++)
    {
        fout << rasp1[i] << " " << rasp2[i] << '\n';
    }
    return 0;
}