#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

vector<pair <int,pair<int,int> > > v1;

vector<pair <int,pair<int,int> > > v2;

vector<pair<int,int> > grandPadre;

int elGrandPadre(int i){
    if(grandPadre[i].first==i)
        return i;
    grandPadre[i].first=elGrandPadre(grandPadre[i].first);
    return grandPadre[i].first;
}

void imprietenire(int i,int j){
    int a=elGrandPadre(i);
    int b=elGrandPadre(j);


    if(grandPadre[a].second>grandPadre[b].second){
        grandPadre[b].first=a;


    }else if(grandPadre[a].second<grandPadre[b].second){
        grandPadre[a].first=b;


    }else{


        grandPadre[a].first=b;
        grandPadre[b].second++;
    }
}

bool c(pair<int,pair<int,int> > i,pair<int,pair<int,int> > j){
    return i.first<j.first;
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");

    long long int n,m,cost,x,y;
    long long int cT=0;
    f>>n>>m;


    for(int i=0;i<m;i++){
        f>>x>>y>>cost;

        v1.push_back(make_pair(cost,make_pair(x,y)));
    }

    for(int i=0;i<=n;i++){
        grandPadre.push_back(make_pair(i,1));
    }
    sort(v1.begin(),v1.end(),c);

    ///*
    for(vector<pair<int,pair<int,int> > >::iterator it=v1.begin(); it<v1.end(); ++it){
        if(grandPadre[(*it).second.first].first!=grandPadre[(*it).second.second].first){
            imprietenire(grandPadre[(*it).second.first].first,grandPadre[(*it).second.second].first);
            cT+=(*it).first;
            v2.push_back(*it);
        }
    }
    g<<cT<<'\n'<<n-1<<'\n';
    for(vector<pair<int,pair<int,int> > >::iterator it=v2.begin(); it<v2.end(); ++it){
        g<<(*it).second.first<<" "<<(*it).second.second<<'\n';
    }
    //*/
    return 0;
}