#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5 + 7;
vector<pair<int, int>> g[nmax];
vector<pair<int, int>> mst[nmax];
int color[nmax];

struct edge {
	int x, y, cost;

	edge() {
		x = y = -1;
		cost = 1024 * 1024 * 1024 + 7;
	}
	edge(int _x, int _y, int _cost) {
		x = _x; y = _y; cost = _cost;
	}
} min_edge[nmax];

void dfs(int node, int c /* culoarea curenta */) // coloreaza
{
	if(color[node] != 0) return;
	color[node] = c;

	for(auto ed : mst[node]) {
		int vec = ed.first;
		dfs(vec, c);
	}
}

#ifdef LOCAL
ifstream in("boruvka.in");
#define cin in
#endif // LOCAL
#ifndef LOCAL
ifstream in("apm.in");
ofstream out("apm.out");
#define cin in
#define cout out
#endif // LOCAL

int main() {
	int n, m; cin >> n >> m;

	for(int i = 0; i < m; i++) {
		int x, y, c; cin >> x >> y >> c;
		g[x].push_back({y, c});
		g[y].push_back({x, c});
	}

	
	set<pair<int, int>> added_edges;
	int cost_total = 0;

	for(int iter = 0; iter < 50 /* ca safety */; iter++) {
		// resetam culori
		for(int i = 1; i <= n; i++) color[i] = 0;

		int culori = 0;
		for(int i = 1; i <= n; i++) {
			if(color[i] == 0) {
				culori++;
				dfs(i, culori);
			}
		}

		#ifdef LOCAL
			cerr << "Culori: " << endl;
			for(int i = 1; i <= n; i++) {
				cerr << i << " -> " << color[i] << endl;
			}
		#endif // LOCAL

		// Am ajuns la MST
		if(culori == 1) break;

		for(int i = 1; i <= culori; i++) {
			min_edge[i] = edge{}; // edge maximal
		}

		for(int i = 1; i <= n; i++) {
			for(auto ed : g[i]) {
				int vec = ed.first;
				int cost = ed.second;

				int col = color[i];

				if(cost < min_edge[col].cost && /* foarte important, nu vrem muchii din aceeasi c.c. */ color[i] != color[vec]) {
					// min_edge[col].x = i;
					// min_edge[col].y = vec;
					// min_edge[col].cost = cost;
				
					min_edge[col] = edge{i, vec, cost};
				}
			}
		}

		for(int i = 1; i <= culori; i++) {
			edge ed = min_edge[i];

			int x = ed.x;
			int y = ed.y; 
			int cost = ed.cost;

			pair<int, int> muchie = {min(x, y), max(x, y)};

			// 2 -> 3 === 3 -> 2
			// {2, 3} =/= {3, 2}
			// {2, 3} === {2, 3}

			if(added_edges.count(muchie) > 0) {
				// muchia deja a fost adaugata
				continue;
			}

			#ifdef LOCAL
				cerr << "Adaugam muchia " << x << " " << y << " " << cost << endl;
			#endif // LOCAL
			mst[x].push_back({y, cost});
			mst[y].push_back({x, cost});
		
			cost_total += cost;
			added_edges.insert(muchie);
		}
	}

	cout << cost_total << '\n';
	cout << n - 1 << '\n';
	for(auto ed : added_edges) {
		cout << ed.first << " " << ed.second << '\n';
	}
}