#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 800;
const int INF = 1000000000;

bool marked[1+MAX_N];

int top;
int apmA[MAX_N], apmB[MAX_N];

int adj[1+MAX_N][1+MAX_N];

int nodeBestEdgeCost[1+MAX_N];
int nodeBestEdgeFrom[1+MAX_N];

void markNode(int nod, int N) {
	marked[nod] = true;
	for(int i = 1; i <= N; ++i)
		if(adj[nod][i] < nodeBestEdgeCost[i]) {
			nodeBestEdgeCost[i] = adj[nod][i];
			nodeBestEdgeFrom[i] = nod;
		}
}

int main() {
	int N, M, sumapm = 0;
	
	FILE *fin = fopen("apm.in", "r");
	fscanf(fin, "%d%d", &N, &M);
	
	for(int i = 1; i <= N; ++i) {
		for(int j = 1; j <= N; ++j)
			adj[i][j] = INF;
		nodeBestEdgeCost[i] = INF;
		nodeBestEdgeFrom[i] = -1;
	}
	
	for(int i = 0; i < M; ++i) {
		int a, b, c;
		fscanf(fin, "%d%d%d", &a, &b, &c);
		adj[a][b] = adj[b][a] = min(adj[a][b], c);
	}
	fclose(fin);

	markNode(1, N);
	for(int i = 2; i <= N; ++i) {
		int bestNode = -1;
		for(int j = 2; j <= N; ++j)
			if(!marked[j] && bestNode == -1)
				bestNode = j;
			else if(!marked[j] && nodeBestEdgeCost[j] < nodeBestEdgeCost[bestNode])
				bestNode = j;
		apmA[top]   = bestNode;
		apmB[top++] = nodeBestEdgeFrom[bestNode];
		sumapm += nodeBestEdgeCost[bestNode];
		markNode(bestNode, N);
	}

	FILE *fout = fopen("apm.out", "w");
	fprintf(fout, "%d\n%d\n", sumapm, top);
	for(int i = 0; i < top; ++i)
		fprintf(fout, "%d %d\n", apmA[i], apmB[i]);
	fclose(fout);
	return 0;
}