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

#define MAXN 200001

ifstream f("apm.in");
ofstream g("apm.out");

int n , m , costTotal , nr;
int grupa[MAXN];

struct muchie
{
    int x,y,cost;
}v[MAXN],sol[MAXN];

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

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m ; i++ )
        f >> v[i].x >> v[i].y >> v[i].cost;
    for (int i = 1; i <= n ; i++ ) grupa[i] = i;
    sort(v+1,v+m+1,cmp);
    int i = 1;
    while ( nr < n )
    {
        if ( grupa[v[i].x] != grupa[v[i].y] )
        {
            costTotal += v[i].cost;
            sol[++nr] = v[i];
            int mn = min(grupa[v[i].x],grupa[v[i].y]);
            int mx = max(grupa[v[i].x],grupa[v[i].y]);
            for ( int j = 1 ; j <= n ; j++ )
                if ( grupa[j] == mx )
                    grupa[j] = mn;
        }
        if ( nr == n-1 ) break;
        i++;
    }
    g << costTotal << "\n" << n-1 << "\n" ;
    for ( i = 1 ; i <= n-1 ; i++ )
        g << sol[i].x << " " << sol[i].y << "\n" ;
    return 0;
}