// apm.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>

struct edge
{
	int x, y, cost;
}e, G[400003], APM[400003];

int M, N, size, sol;

int father[200003], rank[200003];

inline int find(int x)
{
	while (x != father[x])
	{
		x = father[x];
	}
	return x;
}

inline int join(int x, int y)
{
	if (rank[x] > rank[y])
	{
		father[y] = x;
	}
	else
	{
		father[x] = y;
	}
	if (rank[x] == rank[y])
	{
		++rank[y];
	}
}

void swap(int i, int j)
{
	/*
	G[i].x ^= G[j].x ^= G[i].x ^= G[j].x;
	G[i].y ^= G[j].y ^= G[i].y ^= G[j].y;
	G[i].cost ^= G[j].cost ^= G[i].cost ^= G[j].cost;
	*/
	e = G[i];
	G[i] = G[j];
	G[j] = e;
}

void quickSort(int left, int right)
{
	int i = left, j = right, mid = (left + right) >> 1;
	int piv = G[mid].cost;
	while (i <= j)
	{
		while (G[i].cost < piv)
		{
			++i;
		}
		while (G[j].cost > piv)
		{
			--j;
		}
		if (i <= j)
		{
			swap(i, j);
			++i;
			--j;
		}
	}
	if (left < j)
	{
		quickSort(left, j);
	}
	if (right > i)
	{
		quickSort(i, right);
	}

}

int Kruskal()
{
	int cost = 0;
	quickSort(0, M - 1);
	for (int i = 1; i <= N; ++i)
	{
		father[i] = i;
	}
	for (int i = 0; i < M; ++i)
	{
		int rx = find(G[i].x);
		int ry = find(G[i].y);
		if (rx != ry)
		{
			cost += G[i].cost;
			APM[++size] = G[i];
			join(rx, ry);
		}
	}
	return cost;
}


int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; ++i)
	{
		scanf("%d %d %d", &G[i].x, &G[i].y, &G[i].cost);
	}

	sol = Kruskal();

	printf("%d\n%d\n", sol, N - 1);
	for (int i = 1; i <= size; ++i)
	{
		printf("%d %d \n", APM[i].x, APM[i].y);
	}

	printf("\n");

	fclose(stdin);
	fclose(stdout);
    return 0;
}