#include <bits/stdc++.h>

using namespace std;

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

bool marked[1+MAX_N];

struct Edge {
	int a, b, c;

	int other(int x) { // Daca ma aflu in nodul x, vreau sa stiu care e celalalt nod de pe muchie
		return a ^ b ^ x;
	}
} edges[1+MAX_M];

struct Node {
	int nod, i;
	bool operator< (const Node& x) const {
		return edges[i].c <  edges[x.i].c ||
		      (edges[i].c == edges[x.i].c && nod < x.nod);
	}
};

vector<int> graph[1+MAX_N];

int bestEdge[1+MAX_N];
set<Node> nodes;

void markNode(int node) {
	marked[node] = true;
	for(auto it: graph[node]) {
		int son = edges[it].other(node);
		if(!marked[son] && edges[it].c < edges[bestEdge[son]].c) {
			nodes.erase({son, bestEdge[son]});
			bestEdge[son] = it;
			nodes.insert({son, bestEdge[son]});
		}
	}
	nodes.erase({node, bestEdge[node]});
}

int top;
int apmA[1+MAX_N], apmB[1+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};
		graph[a].push_back(i);
		graph[b].push_back(i);
	}
	edges[M] = {0, 0, INF};

	for(int i = 1; i <= N; ++i) {
		bestEdge[i] = M;
		nodes.insert({i, bestEdge[i]});
	}
	fclose(fin);

	markNode(1);
	for(int i = 2; i <= N; ++i) {
		int nod = nodes.begin()->nod, edge = nodes.begin()->i;

		sumapm += edges[edge].c;
		apmA[top] = edges[edge].a;
		apmB[top++] = edges[edge].b;

		markNode(nod);
	}

	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;
}