#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
#define int long long

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

struct edge {
	int from, to, cost;

	edge() { from = to = -1; cost = 1e9; }
	edge(int _from, int _to, int _cost) { 
		if(_from > _to) swap(_from, _to);
		from = _from; to = _to; cost = _cost;
	}
	bool operator<(const edge& other) const {
		if(cost != other.cost) return cost < other.cost;
		if(from != other.from) return from < other.from;
		return cost < other.cost;
	}
	bool operator==(const edge& other) const {
		return from == other.from && to == other.to && cost == other.cost;
	}
};

edge min_per_color[nmax];

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

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

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

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	/* edge x = edge(1, 2, 10); // vreau ca cele doua sa fie egale
	edge y = edge(2, 1, 10);
	cerr << (x == y) << endl; */

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

	// Boruvka

	set<edge> mst_edges;
	int sum = 0;
	for(int rep = 0; rep < 20 /* log n */; rep++) {
		for(int i = 0; i < nmax; i++) {
			color[i] = 0;
			min_per_color[i] = edge(-1, -1, 1024 * 1024 * 1024); // cost foarte mare
		}

		int cnt_color = 0;
		for(int i = 1; i <= n; i++) {
			if(color[i] == 0) {
				cnt_color++;
				dfs(i, cnt_color); 
			}
			// cerr << "COLOR: " << i << " " << color[i] << endl;
		}	

		// am folosit culori de la 1 ... cnt_color
	
		for(int i = 1; i <= n; i++) {
			for(auto out_edge : g[i]) {
				int vec = out_edge.first;
				int cost = out_edge.second;

				if(color[i] == color[vec]) continue;

				min_per_color[color[i]] = min(min_per_color[color[i]], edge(i, vec, cost));
			}
		}

		if(cnt_color == 1) break; // avem un singur arbore in padure, care contine toate nodurile

		for(int c = 1; c <= cnt_color; c++) {
			edge to_add = min_per_color[c];
			// cerr << "C: " << c << " " << to_add.from << " " << to_add.to << " " << to_add.cost << endl;

			if(mst_edges.count(to_add) == 1) continue;
			// cerr << to_add.from << " " << to_add.to << " " << to_add.cost << endl;

			sum += to_add.cost;

			mst_edges.insert(to_add);
			mst[to_add.from].push_back({to_add.to, to_add.cost});
			mst[to_add.to].push_back({to_add.from, to_add.cost});
		}
	}

	cout << sum << '\n' << n - 1 << '\n';

	for(auto e : mst_edges) cout << e.from << " " << e.to << '\n';
}