/*
#include <iostream>
#include <vector>
using namespace std;
vector<int>lungimeArbore,radacina;
int gasesteRadacina(int nod){
    if(radacina[nod]!=nod){
        radacina[nod]=gasesteRadacina(radacina[nod]);
    }
    return radacina[nod];
}
int main()
{
   int n,m;
   cin>>n>>m;
   lungimeArbore.resize(n+1);
   radacina.resize(n+1);
   for(int i=1;i<=n;i++){
    lungimeArbore[i]=1;
    radacina[i]=i;
   }
   for(int i=1;i<=m;i++){
    int operatie,a,b;
    cin>>operatie>>a>>b;
    if(operatie==1){
        int x=gasesteRadacina(a);
        int y=gasesteRadacina(b);
        if(lungimeArbore[x]>lungimeArbore[y]){
            lungimeArbore[x]+=lungimeArbore[y];
            radacina[x]=radacina[y];
            lungimeArbore[y]=0;
        }else{
            lungimeArbore[y]+=lungimeArbore[x];
            radacina[y]=radacina[x];
            lungimeArbore[x]=0;
        }
    }else{
        int x=gasesteRadacina(a);
        int y=gasesteRadacina(b);
        if(x==y){
            cout<<"DA"<<'\n';
        }else{
            cout<<"NU"<<'\n';
        }
    }
   }
    return 0;
}
*/
#include <fstream>
#include<vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
 struct muchie{
    int x,y,c;
};
bool cmp(muchie secundara,muchie principala){
return secundara.c<principala.c;
}
vector<int>radacina,lungimeArbore;
vector<muchie>v;
vector<pair<int,int>>raspuns;
int gasesteRadacina(int nod){
    if(radacina[nod]!=nod){
        radacina[nod]=gasesteRadacina(radacina[nod]);
    }
    return radacina[nod];
}
int main(){
    int n,m;
    cin>>n>>m;
    radacina.resize(n+1);
    lungimeArbore.resize(n+1);
    for(int i=1;i<=n;i++){
        lungimeArbore[i]=1;
        radacina[i]=i;
    }
    v.resize(m);
    for(int i=0;i<m;i++){
       cin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v.begin(),v.end(),cmp);
 int cost=0;
 for(int i=0;i<m;i++){
    int a=gasesteRadacina(v[i].x);
    int b=gasesteRadacina(v[i].y);
    if(radacina[a]==radacina[b]){
        continue;
    }else{
    cost+=v[i].c;
    raspuns.push_back({v[i].y,v[i].x});
    if(lungimeArbore[a]>lungimeArbore[b]){
        lungimeArbore[a]+=lungimeArbore[b];
        radacina[b]=radacina[a];
        lungimeArbore[b]=0;
    }else{
       lungimeArbore[b]+=lungimeArbore[a];
        radacina[a]=radacina[b];
        lungimeArbore[a]=0;
    }
    }
 }
 cout<<cost<<'\n';
 cout<<raspuns.size()<<'\n';
 for(int i=0;i<raspuns.size();i++){
    cout<<raspuns[i].first<<" "<<raspuns[i].second<<'\n';
 }

}