#include <iostream>
#include <algorithm>

using namespace std;

const int NMAX = 2e5;
const int MMAX = 4e5;

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

int n;
int m;
muchie mch[MMAX + 5];
int mchApm[NMAX + 5];
int repr[NMAX + 5];
int sz[NMAX + 5];

bool cmp(muchie m1, muchie m2) {
	return m1.cost < m2.cost;
}

int getRepr(int nod) {
	while (nod != repr[nod])
		nod = repr[nod];
	return nod;
}

void unionRepr(int r, int nod) {
	while (nod != repr[nod]) {
		int rNod = repr[nod];
		repr[nod] = r;
		nod = rNod;
	}
	repr[nod] = r;
}

int kruskal() {
	int mchAlese = 0;
	int costApm = 0;

	for (int i = 1; i <= m; i++) {
		int r1 = getRepr(mch[i].a);
		int r2 = getRepr(mch[i].b);

		if (r1 != r2) {
			mchApm[++mchAlese] = i;
			costApm += mch[i].cost;
			if (sz[r1] < sz[r2]) {
				unionRepr(r2, mch[i].a);
				sz[r2] += sz[r1];
			}
			else {
				unionRepr(r1, mch[i].b);
				sz[r1] += sz[r2];
			}

			if (mchAlese == n - 1)
				return costApm;
		}
	}

	return costApm;
}

int main() {
	// freopen("grafpond.in", "r", stdin);
	// freopen("grafpond.out", "w", stdout);
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++)
		scanf("%d %d %d", &mch[i].a, &mch[i].b, &mch[i].cost);
	for (int i = 1 ; i <= n; i++) {
		repr[i] = i;
		sz[i] = 1;
	}

	sort(mch + 1, mch + m + 1, cmp);

	int costApm = kruskal();
	printf("%d\n%d\n", costApm, n - 1);
	for (int i = 1; i < n; i++)
		printf("%d %d\n", mch[mchApm[i]].a, mch[mchApm[i]].b);

  return 0;
}