#include <cstdio>
#include <algorithm>

using namespace std;

struct Side
{
    int x, y, p;
}
v[400001];

struct Solution
{
    int x, y;
}
s[200001];

int t[200001], h[200001];
int n, m, r, price;

inline void Init( int vect[] )
{
    int i;

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

inline int GetF( int k )
{
    while( t[k]!=k )
        k=t[k];

    return k;
}

inline int UnionF( int a, int b )
{
    int ta=GetF(a);
    int tb=GetF(b);

    if( ta!=tb )
    {
        if( h[ta]==h[tb] )
        {
            h[ta]++;
            t[tb]=ta;
        }
        else
            if( h[ta]<h[tb] )
                t[ta]=tb;
            else
                t[tb]=ta;

        return 1;
    }

    return 0;
}

bool cmp( Side a, Side b )
{
    return a.p<b.p;
}

void Read( )
{
    int i;

    scanf( "%d%d", &n, &m );

    for( i=1;i<=m;i++ )
        scanf( "%d%d%d", &v[i].x, &v[i].y, &v[i].p );
}

void Solve( )
{
    int i;

    for( i=1;i<=m;i++ )
        if( UnionF(v[i].x,v[i].y) )
        {
            price+=v[i].p;

            r++;
            s[r].x=v[i].x;
            s[r].y=v[i].y;
        }
}

void Print( )
{
    int i;

    printf( "%d\n%d\n", price, n-1 );

    for( i=1;i<=r;i++ )
        printf( "%d %d\n", s[i].x, s[i].y );
}

int main()
{
    freopen( "apm.in", "r", stdin );
    freopen( "apm.out", "w", stdout );

    Read();

    Init(t);
    Init(h);

    sort(v+1,v+m+1,cmp);

    Solve();

    Print();

    return 0;
}