// Algoritmul lui Kruskal - O(M log M)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int MAX_N = 2e5, MAX_M = 4e5;

struct muchie
{
	int x, y;
	short cost;
} v[MAX_N + 1];

inline bool cmp(muchie a, muchie b)
{
	if (a.cost > b.cost)
		return 0;
	return 1;
}

class DSU
{
	private:
		int n;
		vector<int> t;
	public:
		// initializare
		void init(int NMAX)
		{
			n = NMAX;
			t.resize(n + 1);
			for (int i = 1; i <= n; i++)
				t[i] = i;
		}
		// radacina nodului x
		int Find(int x)
		{
			if (t[x] == x)
				return x;
			return t[x] = Find(t[x]);
		}
		// reuniunea a doua multimi
		void Union(int a, int b)
		{
			a = Find(a);
			b = Find(b);
			t[b] = a;
		}
};

int n, m, k;
long long costMin;
vector<pair<int, int>> sol;

int main()
{
	f >> n >> m;

	for (int i = 0; i < m; i++)
		f >> v[i].x >> v[i].y >> v[i].cost;

	sort(v, v + m, cmp);

	DSU s;
	s.init(n);

	for (int i = 0; i < m; i++)
		if (s.Find(v[i].x) != s.Find(v[i].y))
		{
			costMin += v[i].cost;
			sol.push_back({v[i].x, v[i].y});
			s.Union(v[i].x, v[i].y);
		}

	g << costMin << '\n' << n - 1 << '\n';

	for (int i = 0; i < n - 1; i++)
		g << sol[i].first << ' ' << sol[i].second << '\n';

	f.close();
	g.close();
	return 0;
}