#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
std::ifstream f("apm.in");
std::ofstream fg("apm.out");
int n, m, a, b, c;

class graf{
public:
    int n, m;

    graf(int n, int m);

    std::vector< bool> viz;
    std::vector< std::vector<int> > mat;
    std::vector<std::vector<int> > lista;
    std::vector<std::vector< std::pair<int, int>> > lista_cost;
    std::vector< std::pair<int, int> > muchii;

    void new_lista_cost( int nod1, int nod2, int cost);

    void afisare_lista_cost();

    void prim();
    int minim( std::vector<int> val ,  std::vector<bool> viz);

};

graf::graf(int n, int m) {
    this->n = n;
    this->m = m;

    std::vector<int> v;
    std::vector< std::pair<int, int>> p;

    for(auto i = 0; i<n ; i++){
        lista_cost.push_back(p);
    }

}

void graf::new_lista_cost(int nod1, int nod2, int cost) {
    lista_cost[nod1].push_back(std::make_pair(nod2, cost));
    lista_cost[nod2].push_back(std::make_pair(nod1, cost));
}

void graf::afisare_lista_cost() {
    for(auto i=1 ; i<n+1 ; i++){
        std::cout<<i<<" - ";
        for( auto j = lista_cost[i].begin() ; j != lista_cost[i].end(); j++){
            std::cout<<" ( "<< j->first<<" , "<<j->second<<" ) ";
        }
        std::cout<<"\n";
    }

    std::cout<<"\n";
}

int graf::minim( std::vector<int> val ,  std::vector<bool> viz){
    int min = INT_MAX;
    int index;

    for(int i = 0 ; i<n ; i++)
        if(!viz[i] && val[i] < min){
            min = val[i];
            index = i;
        }

    return index;
}

void graf::prim(){
    std::vector<int> tata;
    std::vector<int> val;
    std::vector<bool> viz;

    for( int i=0 ; i<n ; i++)
    {
        val.push_back(INT_MAX);
        viz.push_back(false);
        tata.push_back(-1);
    }

    val[0] = 0;

    for(int i = 0 ; i<n ; i++){
        int vecin = minim( val, viz);

        viz[vecin] = true;

        for( auto j = lista_cost[vecin].begin() ; j != lista_cost[vecin].end(); j++){
            auto nod = j->first;
            auto cost = j->second;
            if( !viz[nod] && cost < val[nod] ){
                tata[nod] = vecin;
                val[nod] = cost;
            }
        }
    }

    int sum = 0, cnt = 0;

    for( int i = 0 ; i< n ; i++){
        for( auto j = lista_cost[i].begin() ; j != lista_cost[i].end(); j++)
            if( j->first  == tata[i]){
                sum = sum + j->second;
                cnt++;
            }
    }

    fg<<sum<<"\n"<<cnt<<"\n";

    for( int i = 1 ; i< n ; i++){
        fg<<tata[i] + 1<< " " <<i+1<<"\n";
    }

}

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

    graf g(n, m);
    for(int i=0 ; i<m ; i++){
        f>>a>>b>>c;
        g.new_lista_cost(a-1, b-1, c);
    }

    g.prim();
    return 0;
}