#include <iostream>
#include <cstdio>
#include <map>
#define Nmax 200005
#define Mmax 400005
using namespace std;
multimap <int,int> S;
multimap <int,int>::iterator it;
int n,m,cost=0,add=0;
int ar[Nmax],nivel[Nmax];
typedef struct muchie{int x;int y;};
muchie V[Mmax],U[Nmax];
void reading(int &n,int &m)
{
     int k,nod1,nod2,dist;
     freopen("apm.in","r",stdin);
     freopen("apm.out","w",stdout);
     scanf("%d %d",&n,&m);
     for(k=1;k<=m;++k)
     {
         scanf("%d %d %d",&nod1,&nod2,&dist);
         V[k].x=nod1;V[k].y=nod2;
         S.insert(make_pair(dist,k));
     }
}
int search(int nod)
{
    while(nod!=ar[nod])
      nod=ar[nod];
      return(nod);
}
void apm()
{
    int i,rad1,rad2,nod1,nod2;
    for(i=1;i<=n;++i) {ar[i]=i;nivel[i]=1;}
    for(it=S.begin();it!=S.end();++it)
    {
         nod1=V[it->second].x;
         nod2=V[it->second].y;
         rad1=search(nod1);
         rad2=search(nod2);
         if (rad1!=rad2)
         {
             cost=cost+it->first;++add;
             U[add].x=nod1;U[add].y=nod2;
             if (nivel[rad1]>nivel[rad2]) ar[rad2]=rad1;
             else if (nivel[rad1]<nivel[rad2]) ar[rad1]=rad2;
             else {ar[rad2]=rad1;++nivel[rad1];}
         }
         if (add==n-1) break;
    }
    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(i=1;i<=n-1;++i)
    printf("%d %d\n",U[i].x,U[i].y);
}
int main()
{
    reading(n,m);
    apm();
    return 0;
}