#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;
const int MAX_M = 400000;

struct Edge {
	int a, b, c;
} edges[MAX_M];

bool marked[1+MAX_N];

int top;
int apm[MAX_N];

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

	marked[1] = true;
	for(int i = 2; i <= N; ++i) {
		int bestEdge = -1;
		for(int j = 0; j < M; ++j)
			if(marked[edges[j].a] + marked[edges[j].b] == 1) { // exact un nod e marcat
				if(bestEdge == -1)
					bestEdge = j;
				else if(edges[j].c < edges[bestEdge].c)
					bestEdge = j;
			}
		marked[edges[bestEdge].a] = marked[edges[bestEdge].b] = true;
		sumapm += edges[bestEdge].c;
		apm[top++] = bestEdge;
	}

	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", edges[apm[i]].a, edges[apm[i]].b);
	fclose(fout);
	return 0;
}