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

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

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

struct mycomparison
{
    bool operator() ( const prique& left , const prique& right )
    {
        return ( left . cost > right . cost );
    }
};

const int MAX = 200005;
int N , M , i , node1 , node2 , cost , MSPCost , j , node;
priority_queue < prique , vector < prique > , mycomparison > lightEdge;
vector < pair < int , int > > edge [ MAX ] , msplist ;
prique ledge;
bool vis [ MAX ];

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

void prim ( int node )
{
    prique init;
    init . source = init . destination = node , init . cost = 0 , vis [ node ] = true;
    lightEdge . push ( init );
    for ( i = 1 ; i <= N ; i ++ )
    {
        ledge = lightEdge . top (); node = ledge . destination;

        //delete all the edges that will create a cycle in the current MSP
        while ( vis [ node ] == true && !lightEdge . empty() )
        {
            ledge = lightEdge . top ();
            lightEdge . pop ();
            node = lightEdge . top () . destination;
        }
        //mark the new edge
        if ( vis [ node ] == false )
        {
            ledge = lightEdge . top ();
            vis [ ledge . destination ] = true;
            lightEdge . pop ();
        }
        else
            node = ledge . source;

        //add the cost of ledge to the total one
        MSPCost += ledge . cost;

        //add the edge to the result list
        msplist . push_back ( make_pair ( ledge . source , ledge . destination ) );

        for ( j = 0 ; j < edge [ node ] . size () ; j ++ )
            if ( vis [ edge [ node ] [ j ] . first ] == false )
            {
                init . source = node , init . destination = edge [ node ] [ j ] .first , init . cost = edge [ node ] [ j ] . second;
                lightEdge . push ( init );
            }
    }
}

void print()
{
    int SIZE = msplist . size();
    //the first edge in msplist is from 1 to 1 with cost 0 so it doesn't count
    fprintf ( g , "%d\n%d\n" , MSPCost , SIZE - 1 );
    for ( i = 1 ; i < SIZE ; i ++ )
        fprintf ( g , "%d %d\n" , msplist [ i ] . first , msplist [ i ] . second );
}

int main()
{
    read();

    //starting node is 1
    prim(1);

    print();

    return 0;
}