#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e5;

int N, M;

struct Edge {
	int u, v, c;
};
vector<Edge> edges;

struct DSU {
	vector<int> parent;
	vector<int> setSize;

	DSU () {
		
	}

	DSU (int N) {
		parent = vector<int> (N);
		setSize = vector<int> (N);
	}

	DSU& operator = (const DSU &_) {
		parent = _.parent;
		setSize = _.setSize;
		return *this;
	}

	void makeSet(int x) {
		parent[x] = x;
		setSize[x] = 1;
	}

	int findSet(int x) {
		if(parent[x] == x) {
			return x;
		}

		return parent[x] = findSet(parent[x]);
	}

	void unionSets(int x, int y) {
		int setX = findSet(x);
		int setY = findSet(y);

		if(setX != setY) {
			if(setSize[setX] < setSize[setY]) {
				parent[setX] = setY;
				setSize[setY] += setSize[setX];
			} else {
				parent[setY] = setX;
				setSize[setX] += setSize[setY];;
			}
		}
	}
};

DSU DS; // <3
vector<Edge> ans;

int main() {
	fin >> N >> M;

	DS = DSU(N + 1);

	for(int i = 1; i <= M; i++) {
		int u, v, c;
		fin >> u >> v >> c;

		edges.push_back({u, v, c});
	}

	sort(edges.begin(), edges.end(), [] (const Edge &a, const Edge &b) {
		return a.c < b.c;
	});

	for(const Edge &edge: edges) {
		int u = edge.u;
		int v = edge.v;

		DS.makeSet(u);
		DS.makeSet(v);
	}

	int cost = 0;
	for(const Edge &edge: edges) {
		int u = edge.u;
		int v = edge.v;
		int c = edge.c;
		
		if(DS.findSet(u) != DS.findSet(v)) {
			DS.unionSets(u, v);
			cost += c;
			ans.push_back(edge);
		}
	}

	fout << cost << '\n' << ans.size() << '\n';
	for(const Edge &edge: ans) {
		fout << edge.u << " " << edge.v << '\n';
	}
	return 0;
}