#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>

using namespace std;

struct ARB{
	int a, b, cost;
};

const int mmax = 400002;
const int nmax = 200002;

ARB arb[mmax];
int ind[mmax], n, m, md[nmax] , res[nmax];

bool mysort(const int &a, const int &b) { return arb[a].cost < arb[b].cost; };
void unire(int a, int b);
bool sameGroup(int a, int b);

int main(){
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d %d", &n, &m);
	
	memset(arb, 0, (m+2) * sizeof(struct ARB));

	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &arb[i].a, &arb[i].b, &arb[i].cost);
		ind[i] = i;
	}

	memset(md, 0, 4 * n + 8);
	sort(ind + 1, ind + m + 1, mysort);
	
	int k = 0,sum = 0;
	for (int i = 1; i <= m; i++) {
		if ( !sameGroup( arb[ind[i]].a, arb[ind[i]].b ) ) {
			//add edge + join grups + update TotalCost
			res[k++] = ind[i];
			unire(arb[ind[i]].a, arb[ind[i]].b);
			sum += arb[ind[i]].cost;
		}
	}

	printf("%d\n%d\n", sum, n - 1);
	for (int i = 0; i < k; i++)
		printf("%d %d\n", arb[res[i]].a, arb[res[i]].b);
	fclose(stdin);
	fclose(stdout);
	return 0;
}


void unire(int a, int b) {
	int ha = 0, hb = 0, aa = a, bb = b;
	while (md[aa] != 0) { aa = md[aa]; ha++; };
	while (md[bb] != 0) { bb = md[bb]; hb++; };

	int root;
	if (ha > hb)	{ root = aa;	md[bb] = root; }
	else			{ root = bb;	md[aa] = root; };

	int tmp;
	aa = a; bb = b;
	while (aa != root)  { tmp = md[aa]; md[aa] = root; aa = tmp; };
	while (bb != root)  { tmp = md[bb]; md[bb] = root; bb = tmp; };
}

bool sameGroup(int aa, int bb) {
	while (md[aa] != 0)  aa = md[aa];
	while (md[bb] != 0)  bb = md[bb];
	return aa == bb;
}