#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <functional>
#include <fstream>
#define maxi 200002

using namespace std;

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

vector<pair<int, int>> adj_list[maxi];
vector<int> visited(maxi,0);
priority_queue<tuple<int, int, int> , vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> tail;
vector<pair<int, int>> way;
int n, m, x, y, c;

long int PrimAlgorithm( int startNode ){

    for( auto it = adj_list[startNode].begin() ; it != adj_list[startNode].end() ; it++ )
    {
        tail.push( make_tuple( it -> second , startNode , it -> first ) );
    }

    long int sum = 0;
    while( !tail.empty() )
    {
        int nodPlecare, nodSosire, cost;
        tie( cost, nodPlecare , nodSosire ) = tail.top();
        tail.pop();

        if( visited[nodSosire] == 1 )
            continue;

        visited[nodPlecare] = 1;
        visited[nodSosire] = 1;
        sum += cost;
        way.push_back( make_pair(nodPlecare , nodSosire) );

        for( auto it = adj_list[nodSosire].begin() ; it != adj_list[nodSosire].end() ; it++ )
        {
            if( visited[it -> first] == 0 )
            {
                tail.push( make_tuple( it -> second, nodSosire, it -> first ));
            }
        }
    }
    return sum;
}

int main()
{
    fin >> n >> m;

    for( int i = 0 ; i < m ; i++ )
    {
        fin >> x >> y >> c;
        adj_list[x].push_back( make_pair( y , c ));
        adj_list[y].push_back( make_pair( x , c ));
    }

    long int sum = PrimAlgorithm(1);
    for( int it = 2 ; it <= n ; it++ )
        if( !visited[it] )
        {
            sum += PrimAlgorithm( it );
        }

    fout << sum << endl;
    fout << way.size() << endl;
    for( auto it : way )
    {
        fout << it.first << " " << it.second << endl;
    }
    return 0;
}