#include <cstdio>
#include <algorithm>

const int NMAX=200001;

struct Muchie
{
 int x,y,c;
};

bool cmp(Muchie A,Muchie B)
{
 return A.c<B.c;
}

Muchie muchii[NMAX];
int sef[NMAX],size[NMAX];

int Find(int x)
{
 if(sef[x]==x)
    return x;
 return sef[x]=Find(sef[x]);
}

void Union(int x,int y)
{
 x=Find(x);
 y=Find(y);
 if(size[x]>size[y])
    {
     sef[y]=x;
     size[x]+=size[y];
    }
 else
    {
     sef[x]=y;
     size[y]+=size[x];
    }
}

std::vector<int> vans;

int main()
{
 FILE *in=fopen("apm.in","r");
 FILE *out=fopen("apm.out","w");

 int n,m;
 fscanf(in,"%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
     {
      fscanf(in,"%d %d %d ",&muchii[i].x,&muchii[i].y,&muchii[i].c);
      sef[i]=i;
     }
 std::sort(muchii+1,muchii+m+1,cmp);

 int ans=0;
 for(int i=1;i<=m;i++)
     {
      if(Find(muchii[i].x)!=Find(muchii[i].y))
         {
          ans+=muchii[i].c;
          Union(muchii[i].x,muchii[i].y);
          vans.push_back(i);
         }
     }
 fprintf(out,"%d\n%d\n",ans,n-1);
 for(auto &i:vans)
     fprintf(out,"%d %d\n",muchii[i].x,muchii[i].y);
 fclose(in);
 fclose(out);
 return 0;
}