#include <cstdio>
#include <algorithm>
#define DIM 400005

using namespace std;

FILE *in,*o;

struct muchie{
	int x,y,c;
}M[DIM];

int n,m,ind;
int h[DIM],tata[DIM],use[DIM],cate,sol[DIM];
void cit()
{
int i;
in=fopen("apm.in","r");
fscanf(in,"%d%d",&n,&m);
for(i=1;i<=m;i++)
	fscanf(in,"%d%d%d",&M[i].x,&M[i].y,&M[i].c);
fclose(in);
}

int comp(muchie a, muchie b)
{
return a.c<b.c;
}

void sortarem()
{
sort(M+1,M+1+m,comp);
}

void reunion(int a, int b)
{
   if(h[a]>h[b])
   {
       tata[b]=a;
   }
   else
       if(h[b]>h[a])
       {
           tata[a]=b;
       }
       else
       {
           tata[b]=a;
           h[a]++;
       }
}

int find(int x)
{
int r=x,aux;
while(tata[r])
{
	r=tata[r];
}
while(tata[x])
{
	aux=tata[x];
	tata[x]=r;
	x=aux;
}
return r;
}

void kruskal()
{
   for(int i=1;i<n;i++)
   {
       for(int j=1;j<=m;j++)
       {
           int a=find(M[j].x);
           int b=find(M[j].y);
           if(a!=b&&use[j]==0)
           {
               use[j]=1;
               ind++;
               sol[ind]=j;
               cate++;
               reunion(a,b);
               break;
           }
       }
  }
}
void afis()
{
o=fopen("apm.out","w");
int s=0;
   for(int i=1;i<=ind;i++)
           s+=M[sol[i]].c;
   fprintf(o,"%d\n%d\n",s,cate);
   for(int i=1;i<=ind;i++)
           fprintf(o,"%d %d\n",M[sol[i]].x,M[sol[i]].y);
fclose(o);
}

int main()
{
cit();
sortarem();
kruskal();
afis();
return 0;
}