// #include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n, m, x, y, c;
int i;
int cost_total=0;
vector <int> tata;
vector<pair<int, int>> muchii_apcm;
vector <int> inaltime;

struct Muchie{
    int x,y; //capetele muchiei
    int c; //costul muchiei

    bool operator<(const Muchie& other) const {
        return c < other.c;
    }
};

vector<Muchie> muchii;

void citire(){
    cin>>n>>m;
    for(i=1; i<= m; i++){
        cin>>x>>y>>c;
        muchii.push_back({x,y,c});
    }
}

void ordonare_muchii(){
    sort(muchii.begin(), muchii.end());
}

void initializare_tata(){
    inaltime.resize(n + 1, 0);
    tata.resize(n + 1);
    for(i=1; i<=n ;i++){
        tata[i]=i;
    }
}

int Find(int nod){
    if(tata[nod]==nod)
        return nod;
    return tata[nod] = Find(tata[nod]);
}

void Union(int x, int y){
    int radacina_x = Find(x);
    int radacina_y = Find(y);
    if (radacina_x != radacina_y)
    {
        if(inaltime[radacina_x]< inaltime[radacina_y]){
            tata[radacina_x]=radacina_y;
        }else if(inaltime[radacina_x]> inaltime[radacina_y]){
            tata[radacina_y]=radacina_x;
        }else{
            tata[radacina_x]=radacina_y;
            inaltime[radacina_y]++;
        }
        
    }
}

void Kruskal_APCM(){
    citire();
    ordonare_muchii();
    initializare_tata();

    for( const auto& muchie : muchii){
        int radacina_x= Find(muchie.x);
        int radacina_y= Find(muchie.y);

        if(radacina_x != radacina_y){
            cost_total+=muchie.c;
            muchii_apcm.push_back({muchie.x, muchie.y});
            Union(muchie.x, muchie.y);

            if(muchii_apcm.size() == n-1){
                break;
            }
        }
    }
}

void afisare(){
    cout<< cost_total<<endl;
    cout<<muchii_apcm.size()<<endl;

    for( const auto& muchie: muchii_apcm){
        cout<< muchie.first <<" "<<muchie.second<<endl;
    }
}

int main(){

    Kruskal_APCM();
    afisare();

    return 0;
}