#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x,y,c;}v[400005];
int daddy[200005],h[200005],viz[400005],ct;
inline bool cmp(muchie A, muchie B)
  {return A.c<B.c;
  }
int Find_big_daddy(int q)
   {while(daddy[q]!=q)q=daddy[q];
    return daddy[q];
   }
void Unite_the_daddies(int p,int q)
    {if(h[Find_big_daddy(p)]<h[Find_big_daddy(q)]){daddy[Find_big_daddy(p)]=daddy[Find_big_daddy(q)];}
       else {daddy[Find_big_daddy(q)]=daddy[Find_big_daddy(p)];
             if(h[p]==h[q])h[p]++;
            }
    }
int s,n,m,i;
int main()
{fin>>n>>m;
 for(i=1;i<=n;i++)
    {daddy[i]=i;h[i]=1;}
 for(i=1;i<=m;i++)
    fin>>v[i].x>>v[i].y>>v[i].c;
 sort(v+1,v+m+1,cmp);
 for(i=1;i<=m;i++)
    {if(Find_big_daddy(v[i].x)!=Find_big_daddy(v[i].y)){s=s+v[i].c;
                                                        Unite_the_daddies(v[i].x,v[i].y);viz[i]=1;ct++;
                                                        if(ct==n-1)break;}
    }
 fout<<s<<"\n"<<n-1<<"\n";
 for(i=1;i<=m;i++)
    {if(viz[i]==1)fout<<v[i].x<<" "<<v[i].y<<"\n";
    }
}