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

#define NMAX 200005
#define MMAX 400005

struct muchie{
    int x, y, c;
} v[ MMAX ];

int sol[ MMAX ];
int mini, parent[ NMAX ];

int radacina( int x );
bool addMuchie( int x, int y );
bool cmp( muchie a, muchie b );


int main()
{

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

    int n, m, i, j, x, y, c;
    vector < pair < int, int > > :: iterator it;

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

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

    for( i = 1; i <= n; ++i ) parent[ i ] = i;
    for( i = 1; i <= m; ++i ){
           if( addMuchie( v[ i ].x, v[ i ].y ) ){
                mini += v[ i ].c;
                sol[ i ] = 1;
           }
    }

    printf("%d\n%d\n",mini,n-1);
    for( i = 1; i <= m; ++i )
        if( sol[ i ] ) printf("%d %d\n",v[ i ].x,v[ i ].y);


    return 0;

}

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

int radacina( int x ){

    while( x != parent[ x ] ) x = parent[ x ];
    return x;

}

bool addMuchie( int x, int y ){

    int rx = radacina( x );
    int ry = radacina( y );

    if( rx != ry ) parent[ rx ] = ry;
    return ( rx != ry );

}