#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, c, x, y, c_min = 0;
vector<int> parent(200001), rang(200001);
vector<pair<pair<int,int>, int> > edges;
vector<pair<int, int> > sol;

struct cmp {
	bool operator()(pair<pair<int,int>, int> x, pair<pair<int,int>, int> y) {
		return x.second < y.second;
	}
};

int find(int n1) {
	int cp = n1, aux;

	while (cp != parent[cp])                    // gasirea capului
		cp = parent[cp];

	while (n1 != parent[n1]) {
		aux = parent[n1];                          // compresia drumurilor
		parent[n1] = cp;
		n1 = aux;
	}

	return cp;
}

void unite(int n1, int n2) {
	if (rang[n1] > rang[n2])
		parent[n2] = n1;
		else parent[n1] = n2;                         // unesc multimea de rang mai mic cu cea de rang mai mare

	if (rang[n1] == rang[n2])
		rang[n2] ++;
}
                                                     // https://www.youtube.com/watch?v=ID00PMy0-vE
int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i ++) {
		parent[i] = i;
		rang[i] = 0;
	}

	for (int i = 1; i <= m; i ++) {
		scanf("%d %d %d", &x, &y, &c);
		edges.push_back(make_pair(make_pair(x, y), c));
	}

	sort(edges.begin(), edges.end(), cmp());

	for (int i = 0; i < edges.size(); i ++) {
		//cout << edges[i].first.first << " " << edges[i].first.second << "  " << edges[i].second << endl;
		if (find(edges[i].first.first) != find(edges[i].first.second)) {
			unite(edges[i].first.first, edges[i].first.second);
			sol.push_back(make_pair(edges[i].first.first, edges[i].first.second));
			c_min += edges[i].second;
		}
	}

	printf("%d\n", c_min);
	printf("%d\n", (int)sol.size());

	for(int i = 0; i < sol.size(); i ++)
		printf("%d %d\n", sol[i].first, sol[i].second);

	return 0;
}