#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int kInf = 1e9;

struct edge_t {
	int u, v, c;
	edge_t() {}
	edge_t(int u, int v, int c): u(u), v(v), c(c) {}
};

vector<edge_t> prim(int s, const vector<vector<pair<int, int>>> &adj) {
	int n = adj.size();
	vector<edge_t> apm;
	vector<int> minEdge(n, kInf), from(n);
	vector<bool> vis(n);
	struct node_t {
		int u, minEdge;
		node_t() {}
		node_t(int u, int minEdge): u(u), minEdge(minEdge) {}
		bool operator <(const node_t &oth) const {
			return minEdge > oth.minEdge;
		}
	};
	priority_queue<node_t> pq;
	minEdge[s] = 0;
	pq.emplace(s, minEdge[s]);
	while(!pq.empty()) {
		auto [u, mn] = pq.top();
		pq.pop();
		if(vis[u]) continue;
		if(u != s) apm.emplace_back(from[u], u, minEdge[u]);
		vis[u] = 1;
		for(const auto &[v, c]: adj[u]) {
			if(c < minEdge[v] && !vis[v]) {
				minEdge[v] = c;
				from[v] = u;
				pq.emplace(v, minEdge[v]);
			}
		}
	}
	return apm;
}

int main() {
	int n, m;
	fin >> n >> m;
	vector<vector<pair<int, int>>> adj(n);
	for(int i = 0; i < m; i++) {
		int u, v, c;
		fin >> u >> v >> c;
		u--; v--;
		adj[u].emplace_back(v, c);
		adj[v].emplace_back(u, c);
	}
	vector<edge_t> apm = prim(0, adj);
	int cost = 0;
	for(const auto &[u, v, c]: apm) {
		cost += c;
	}
	fout << cost << '\n' << apm.size() << '\n';
	for(const auto &[u, v, c]: apm) {
		fout << u + 1 << " " << v + 1 << '\n';
	}
	return 0;
}