#include <fstream>
#include <algorithm>
#include<vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct muchie{
    int nod1,nod2,cost;
};
bool cmp(muchie a,muchie b){
    return a.cost<b.cost;
}
vector<muchie>muchii;
vector<int>cardinal,tata;
vector<pair<int,int>>rasp;
int gasesteRadacina(int nod){
    while(tata[nod]!=nod){
        nod=tata[nod];
    }
    return nod;
}
void uneste(int nodA,int nodB){
    nodA=gasesteRadacina(nodA);
    nodB=gasesteRadacina(nodB);

    if(cardinal[nodA]>cardinal[nodB]){
        cardinal[nodA]+=cardinal[nodB];
        tata[nodB]=tata[nodA];
        cardinal[nodB]=0;

    }else{
        cardinal[nodB]+=cardinal[nodA];
        tata[nodA]=tata[nodB];
        cardinal[nodA]=0;

    }
}
int n,m;
int main(){
    cin>>n>>m;
    muchii.resize(m+1);
    cardinal.resize(n+1,1);
    tata.resize(n+1);
    for(int i=1;i<=m;i++){
        cin>>muchii[i].nod1>>muchii[i].nod2>>muchii[i].cost;
    }
    for(int i=1;i<=n;i++){
        tata[i]=i;
    }
    sort(muchii.begin()+1,muchii.end(),cmp);
    int nodA,nodB,cost=0;
    for(int i=1;i<=m;i++){
        nodA=gasesteRadacina(muchii[i].nod1);
        nodB=gasesteRadacina(muchii[i].nod2);
        if(nodA==nodB){
            continue;
        }
        uneste(muchii[i].nod1,muchii[i].nod2);
        rasp.push_back({muchii[i].nod1,muchii[i].nod2});
        cost+=muchii[i].cost;
    }
    cout<<cost<<'\n';
    cout<<rasp.size()<<'\n';
    for(int i=0;i<rasp.size();i++){
        cout<<rasp[i].first<<" "<<rasp[i].second<<'\n';
    }
    muchii.clear();
    cardinal.clear();
    tata.clear();
}