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

	bool operator< (const Edge& x) const {
		return c > x.c;
	}
} edges[1+MAX_M];

priority_queue<Edge> pq;
vector<int> graph[1+MAX_N];

void markNode(int node) {
	marked[node] = true;
	for(auto it: graph[node])
		pq.push(edges[it]);
}

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);
	}
	fclose(fin);

	markNode(1);
	while(!pq.empty()) {
		Edge edge = pq.top();
		pq.pop();

		if(marked[edge.a] + marked[edge.b] == 1) { // Exact un nod e marcat
			apmA[top] = edge.a;
			apmB[top++] = edge.b;
			sumapm += edge.c;
			if(!marked[edge.a])
				markNode(edge.a);
			else
				markNode(edge.b);
		}
	}

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