#include <cstdio>

#define MMAX 400001
#define DMAX 200001

using namespace std;

FILE * intrare = fopen("apm.in","r");
FILE * iesire = fopen("apm.out","w");

struct comp
{
    int x, y;
    int c;
} G[MMAX];

int m, n;
int C[DMAX];
int h[DMAX];
int costmin;
comp sol[DMAX];

void citire();
int Find(int x);
void Union(int x, int y);
void InsertHeap(comp c);
comp ExtractHeap();
void kruskal();

int main()
{
  int i;
  citire();
  kruskal();
  fprintf(iesire,"%d\n",costmin);
  fprintf(iesire,"%d\n",n - 1);
  for(i = 1; i <= n - 1; i++)
    fprintf(iesire,"%d %d\n", sol[i].x, sol[i].y);
  fclose(iesire);
  return 0;
}

void citire()
{
  int i, mch;
  fscanf(intrare,"%d %d",&n,&mch);
  m = 1;
  for(i = 1;i <= mch;i++)
  {
    comp c1;
    fscanf(intrare,"%d %d %d", &c1.x,&c1.y,&c1.c);
    InsertHeap(c1);
  }
  
}

void kruskal()
{
  int i, c1, c2;
  comp c;
  for(i = 0; i < n - 1;)
  {
    c = ExtractHeap();
    c1 = Find(c.x);
    c2 = Find(c.y);
    if (c1 != c2)
    {
      i++;
      sol[i] = c;
      costmin += c.c;
      Union(c1,c2);
    }
  }
}

int Find(int x)
{
	int aux=x;
	int a;
	while (C[aux])
		aux = C[aux];
	while (C[x])
	{
		a=x;
		x=C[x];
		C[a]=aux;
	}
	return x;
}

void Union(int i, int j)
{
	if (h[i] < h[j])
		C[i]=j;
	if (h[i] > h[j])
		C[j]=i;
	if (h[i] == h[j])
		C[i]=j, 
	h[j]++;
}

void InsertHeap(comp x)
{
  int i, j;
  comp aux;
  m++;
  G[m] = x;
  i = m; j = m/ 2;
  while(i > 1 && G[j].c > G[i].c)
  {
    aux = G[i];
    G[i] = G[j];
    G[j] = aux;
    i = j; j = i / 2;
  }
}

comp ExtractHeap()
{
	int tata, fiu;
	comp aux, x;
	tata = 1; fiu = 2; x = G[1];
	G[1] = G[m];
	m--;
	while (fiu+1<=m)
	{
		if (fiu+2<=m)
			fiu = G[fiu].c>G[fiu+1].c?fiu+1:fiu;
		if (G[tata].c>G[fiu].c)
		{
			aux = G[tata];
			G[tata] = G[fiu];
			G[fiu] = aux;
			tata = fiu; fiu*=2;
		}
		else
			break;
	}
	return x;
}