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

#define nrmax 200001

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

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

int n , m;

bool criteriu ( muchie a , muchie b )
{
    return a.c < b.c;
}
int x , y , z , S ;
vector < int >  C(nrmax)  ;
vector < muchie > v , sol ;

int main()
{
    f >> n >> m;
    int t = m;
    for ( ; m-- ; )
    {
        f >> x >> y >> z;
        muchie a;
        a.x = x;
        a.y = y;
        a.c = z;
        C[x] = x;
        C[y] = y;
        v.push_back(a);
    }
    sort ( v.begin() , v.end() , criteriu ) ;
    for ( int i = 0 ; i < t and n; i++ )
    {
        if ( C[v[i].x] != C[v[i].y] )
        {
            n--;
            S += v[i].c;
            sol.push_back(v[i]);
            int minim = min (C[v[i].x] , C[v[i].y] );
            int maxim = max (C[v[i].x] , C[v[i].y] );
            replace(C.begin(), C.end() , maxim , minim ) ;
        }
    }
    g << S << "\n" ;
    g << sol.size() << "\n" ;
    for ( int i = 0 ; i < sol.size() ; i++ )
        g << sol[i].x << " " << sol[i].y  << "\n" ;
    return 0;
}