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

FILE *f = fopen ( "apm.in" , "r" ) , *g = fopen ( "apm.out" , "w" );

struct edgeType
{
    int source , destination , cost;
};

const int MAX = 200005;
edgeType edge [ MAX ];
int node1 , node2 , cost , N , M , source_parent , destination_parent , i , father [ MAX ] , root , MSPCost;
vector < pair < int , int > > msplist;

void read()
{
    fscanf ( f , "%d %d" , &N , &M );
    for ( i = 0 ; i < M ; i ++ )
    {
        fscanf ( f , "%d %d %d" , &node1 , &node2 , &cost );
        edge [ i ] . source = node1 , edge [ i ] . destination = node2 , edge [ i ] . cost = cost;
    }
}

bool cmp ( edgeType x , edgeType y )
{
    return ( x . cost < y . cost );
}

int parent ( int node , int &root )
{
    if ( father [ node ] )
    {
        parent ( father [ node ] , root );
        father [ node ] = root;
    }
    else
        root = node;
    return root;
}

void join ( int ltree , int rtree )
{
    father [ rtree ] = ltree;
}

void combine()
{
    for ( i = 0 ; i < M ; i ++ )
    {
        //parent ( i ) finds the root of the tree containing node i and connects all the nodes to the root directly
        source_parent = parent ( edge [ i ] . source , root );
        destination_parent = parent ( edge [ i ] . destination , root );
        if ( source_parent != destination_parent )
        {
            join ( source_parent , destination_parent );
            msplist . push_back ( make_pair ( edge [ i ] . destination , edge [ i ] . source ) );
            MSPCost += edge [ i ] . cost;
        }
    }
}

void print()
{
    fprintf ( g , "%d\n%d\n" , MSPCost , N - 1 );
    for ( i = 0 ; i < N - 1 ; i ++ )
        fprintf ( g , "%d %d\n" , msplist [ i ] . first , msplist [ i ] . second );
}

int main()
{
    read();

    sort ( edge , edge + M , cmp );

    combine();

    print();
    return 0;
}