#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int tata[400001],n,m,i,j,k,r1,r2,S,r;
struct nr{
   int x;
   int y;
   int c;
   int viz;
}V[400001];
int cmp(nr a, nr b){
       return a.c<b.c;
}
int Tata(int x){
    while(tata[x]>0)
          x=tata[x];
    return x;
}
int main()
{fin>>n>>m;
for(i=1;i<=m;i++){
    fin>>V[i].x>>V[i].y>>V[i].c;
}
for(i=1;i<=n;i++)
    tata[i]=-1;
sort(V+1,V+m+1,cmp);
k=0; S=0;
for(i=1;i<=m&&k<n;i++){
    r1=Tata(V[i].x);
    r2=Tata(V[i].y);
    if(r1!=r2){
       V[i].viz=1;
       S=S+V[i].c;
       k++;
       if(tata[r1]<tata[r2]){
          tata[r1]+=tata[r2];
          tata[r2]=r1;
       }
       else{
        tata[r2]+=tata[r1];
        tata[r1]=r2;
       }
    }
}
fout<<S<<"\n"<<k<<"\n";
for(i=1;i<=m;i++)
    if(V[i].viz==1){
       fout<<V[i].x<<" "<<V[i].y<<"\n";
}

    return 0;
}