#include <fstream>
#include <algorithm>
#define x first
#define y second
using namespace std;
ofstream fout ("apm.out");
ifstream fin ("apm.in");
pair < int , pair < int , int > > v[400005];
pair < int , int > rasp[200005];
int parinte[200005];
int n,m,i,a,b,c,cost,cnt;
int dsu( int a )
{
    if( parinte[ a ] == a )
        return a;
    return parinte[ a ] = dsu( parinte[ a ] );
}
int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>a>>b>>c;
        v[ i ].x = c;
        v[ i ].y.x = a;
        v[ i ].y.y = b;
    }
    for( i = 1 ; i <= n ; i++ )
        parinte[ i ] = i;
    sort( v + 1 , v + m + 1 );
    for( i = 1 ; i <= m ; i++ )
    {
        if( dsu( v[ i ].y.x ) != dsu( v[ i ].y.y ) )
        {
            parinte[ dsu( v[ i ].y.x ) ] = parinte[ dsu( v[ i ].y.y ) ];
            cost += v[ i ].x;
            rasp[ ++cnt ] = { v[ i ].y.x , v[ i ].y.y };
        }
    }
    fout<<cost<<'\n'<<n - 1<<'\n';
    for( i = 1 ; i < n ; i++ )
        fout<<rasp[ i ].x<<" "<<rasp[ i ].y<<'\n';
}