#include <iostream>
#include <map>
#include <cstdio>
#define Nmax 200005
using namespace std;
multimap<int,int> S;
multimap<int,int>::iterator it;
int n,ar[Nmax],nivel[Nmax];
typedef struct muchie{int x,y;};
muchie v[Nmax],u[Nmax];
void reading(int &n)
{
    int i,m,nod1,nod,z;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&nod1,&nod,&z);
        v[i].x=nod1;v[i].y=nod;
        S.insert(make_pair(z,i));
    }
}
int search(int nod)
{
      while(nod!=ar[nod]) nod=ar[nod];
      return(nod);
}
void apm()
{
     int i,nod1,nod2,rad1,rad2,cost=0,add=0;
     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);
    apm();
    return 0;
}