#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back

using namespace std;

const int maxn = 400100;

int comp[maxn], X[maxn], Y[maxn], C[maxn], replaceArray[maxn];
int N, M, ANS, IND[maxn];
vector<int> VANS;

int find(int i) {
	return replaceArray[comp[i]] != 0 ? replaceArray[comp[i]] : comp[i] ;
}

void reuniune(int x, int y) {
	replaceArray[comp[x]] = find(y);
}

bool cmpf(int i,int j) {
	return(C[i] < C[j]); 
}

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

	scanf("%d %d\n",&N,&M);

	for(int i = 1;i <= M;++i) {
		scanf("%d %d %d\n",&X[i],&Y[i],&C[i]);

		IND[i] = i;
	}

	for(int i = 1; i <= N; i++) comp[i] = i;

	sort(IND + 1, IND + M + 1, cmpf);

	for(int i = 1;i <= M; ++i) {
		int muchie = IND[i];

		int x = X[muchie];
		int y = Y[muchie];
		int cost = C[muchie];

		int cX = find(x);
		int cY = find(y);

		if (cX != cY){
			ANS += cost;

			int maxim = cX > cY ? cX : cY;
			int minim = cX > cY ? cY : cX;

			reuniune(maxim, minim);

			VANS.pb(muchie);
		}
	}

	printf("%d\n",ANS);
	printf("%d\n",N - 1);

	for(int i = 0;i < N - 1; ++i) {
		printf("%d %d\n", Y[VANS[i]], X[VANS[i]]);
	}

return 0;
}