#include <fstream>
#include <algorithm>

#define f first
#define s second

using namespace std;

ifstream F("apm.in");
ofstream G("apm.out");

int n, m, c, x, y, Tx, Ty, t[200003], k;
long long S;
pair<int, pair<int, int> > v[200003];
pair<int, int> sol[400003];

int Find( int x )
{
    if( x == t[x] ) return x;
    return t[x] = Find(t[x]);
}

int main()
{
    F >> n >> m;
    for(int i = 1; i <= n; ++ i) t[i] = i;
    for(int i = 1; i <= m; ++ i )
    {
        F >> x >> y >> c;
        v[i] = {c, {x, y}};
    }
    sort(v+1, v+m+1);
    for( int i = 1; i <= m; ++ i )
    {
        c = v[i].f;
        x = v[i].s.f;
        y = v[i].s.s;
        Tx = Find(x);
        Ty = Find(y);
        if( Tx > Ty ) t[y] = Tx;
        else if( Tx < Ty ) t[x] = Ty;
        if( Tx != Ty )
        {
            S += c;
            sol[++k] = v[i].s;
        }
    }
    G << S << '\n' << k << '\n';
    for(int i = 1; i <= k; ++ i)
        G << sol[i].f << " " << sol[i].s << '\n';
    return 0;
}