#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX=400005;
pair <int , int> P[NMAX];
int k;
int n,m,total,tt[NMAX],rg[NMAX];
struct muchie{int x,y,cost;} v[NMAX];
bool compara(muchie a, muchie b){return a.cost<b.cost;}
void citire(){
fin>>n>>m;
for(int i=1;i<=m;i++){fin>>v[i].x>>v[i].y>>v[i].cost;
}
sort(v+1,v+m+1,compara);
for(int i=1;i<=n;i++){tt[i]=i;
                     rg[i]=1;
}

}
int Find(int nod){
while(tt[nod]!=nod){nod=tt[nod];}
return nod;
}
void unire(int x,int y){if(rg[x]<rg[y]){tt[x]=y;}
                        if(rg[x]>rg[y]){tt[y]=x;}
                        if(rg[x]==rg[y]){tt[x]=y;
                                          rg[y]++;}
                        }
void rezolva(){for(int i=1;i<=m;i++){if(Find(v[i].x)!= Find(v[i].y)){
                                                                    unire(Find(v[i].x),Find(v[i].y));
                                                                     P[++k].first=v[i].x;
                                                                     P[k].second=v[i].y;
                                                                     total+=v[i].cost;}}}

int main()
{
    citire();
    rezolva();
    fout<<total<<"\n"<<n-1<<"\n";
    for(int i=1 ; i<=k;i++){fout<<P[i].second<<" "<<P[i].first<<"\n";}
}