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

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

struct cel{int x,y,c,f;}q[400010];
int freq[200010],cost[200010],s[200010],i,j,n,m,k,ans,ans2,X,Y;

bool cel(cel a, cel b)
{
    return a.c<b.c;
}

int findParent(int x)
{
    while( s[ x ] != x )
        x = s[ x ];
    return x;
}

int main()
{
    fin>>n>>m;
    for(i=1 ; i<=m ; ++i)
        fin>>q[ i ].x>>q[ i ].y>>q[ i ].c;

    sort(q+1,q+m+1,cel);

    for(i=1 ; i<=n ; ++i)
        s[ i ] = i;

    while( ans2 != n - 1 )
    {
        ++k;
        X = findParent( q[ k ].x );
        Y = findParent( q[ k ].y );
        if( X != Y )
        {
            if( X < Y )
                s[ X ] = Y;
            else
                s[ Y ] = X;
            ans += q[ k ].c;
            q[ k ].f = 1;
            ++ans2;
        }
    }
    fout<<ans<<'\n'<<ans2<<'\n';
    for(i=1 ; i<=m ; ++i)
        if( q[ i ].f == 1 )
            fout<<q[ i ].x<<' '<<q[ i ].y<<'\n';

return 0;
}