#include<stdio.h>
#include<algorithm>
using namespace std;
#define NMAX 200005

int N,M;
int x[NMAX], y[NMAX], c[NMAX], ind[NMAX], parent[NMAX], rank[NMAX], v[NMAX];

int cmp(int a, int b)
{
	if(c[a] < c[b]) return 1;
	return 0;
}

void MakeSet(int x)
{
	parent[x] = x;
	rank[x] = x;
}

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


void Union(int xRoot, int yRoot)
{
	//xRoot = Find(x[ind[i]]);
	//yRoot = Find(y[ind[i]]);
	
	if(rank[xRoot] > rank[yRoot])
		{
			parent[yRoot] = xRoot;
			rank[xRoot] += rank[yRoot];
		}
	  else if(rank[xRoot] <= rank[yRoot])
		  {
			  parent[xRoot] = yRoot;
			  rank[yRoot] += rank[xRoot];
		  }
}


int main()
{ int i;
	
	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", &x[i], &y[i], &c[i]);
		ind[i] = i;
	}
	
	for(i = 1; i <= N; i++)
		MakeSet(i);
	
	sort(ind+1, ind + M + 1, cmp);
	
	int cont = 0;
	int	total = 0;
	
	for(i = 1; i <= M; i++)
	{
		int xRoot = Find(x[ind[i]]);
		int yRoot = Find(y[ind[i]]);
		
		if(xRoot != yRoot)
		{
			Union(xRoot, yRoot);
			cont++;
			v[cont] = ind[i];
			total += c[ind[i]];
		}
	}
	
	printf("%d\n%d\n", total, cont);
	
	for(i = 1; i <= cont; i++)
		printf("%d %d\n", y[v[i]], x[v[i]]);
	
	return 0;
}