#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1 + 2e5, M = 4e5;

class UnionFind{
	int T[N], D[N];

public:
	UnionFind(){
		memset(T, -1, sizeof(T));
		for (int i = 0; i < N; i++)
			D[i] = 1;
	}
	inline int root(int x){
		return T[x] == -1 ? x : T[x] = root(T[x]);
	}
	inline bool merge(int x, int y){
		x = root(x); y = root(y);
		if ( x == y ) return false;

		if ( D[x] < D[y] ){
			T[x] = y;
			D[y] += D[x];
		} else {
			T[y] = x;
			D[x] += D[y];
		}
		return true;
	}
};
struct Edge{
	int x, y, c;
	inline bool operator<(const Edge& E) const {
		return c < E.c;
	}
};

Edge edge[M];
UnionFind P;

int main(){
	ifstream in("apm.in");
	ofstream out("apm.out");
	int n, m;

	in >> n >> m;
	for (int i = 0; i < m; i++)
		in >> edge[i].x >> edge[i].y >> edge[i].c;


	vector< pair<int, int> > sol;
	sort(edge, edge + m);

	int cost = 0;
	for (int i = 0; sol.size() != n - 1; i++)
		if ( P.merge( edge[i].x, edge[i].y ) ){
			sol.emplace_back(edge[i].x, edge[i].y);
			cost += edge[i].c;
		}

	out << cost << '\n' << n - 1 << '\n';
	for (auto p : sol)
		out << p.first << ' ' << p.second << '\n';
	return 0;
}