//

//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
//#define _USE_MATH_DEFINES

#include <iostream>
#include <fstream>
#include <vector>
//#include <cstring>
//#include <cmath>
//#include <bitset>
//#include <queue>
//#include <stack>
//#include <utility>
#include <algorithm>
//#include <string>
//#include <map>
//#include <unordered_map>
//#include <set>
//#include <unordered_set>
//#include <cstdint>
//#include <climits>
//#include <iomanip>
//#include <cstdio>
//#include <tuple>

using namespace std;

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

const int NRMAX = 200000;
const int MMAX = 400000;

struct Muchie
{
	int cost;
	int from;
	int to;

	bool operator<(const Muchie& other) const
	{
		return cost < other.cost;
	}
};

Muchie mu[MMAX];
vector <int> v[100005];
int b[100005];

int main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	//cout.tie(nullptr);

	int n, m, i, rezc = 0;
	vector<pair<int, int>> rez;

	fin >> n >> m;
	for (i = 0; i < m; ++i)
	{
		fin >> mu[i].from >> mu[i].to >> mu[i].cost;
	}

	sort(mu, mu + m);

	for (i = 1; i <= n; ++i)
	{
		b[i] = i;
		v[i].push_back(i);
	}

	for (i = 0; i < m; ++i)
	{
		if (b[mu[i].from] != b[mu[i].to])
		{
			int xx = b[mu[i].from];
			int yy = b[mu[i].to];
			if (v[xx].size() < v[yy].size())
				swap(xx, yy);

			for (const auto& it : v[yy])
			{
				b[it] = xx;
				v[xx].push_back(it);
			}

			rezc += mu[i].cost;
			rez.emplace_back(mu[i].from, mu[i].to);
		}
	}

	fout << rezc << "\n";
	fout << rez.size() << "\n";
	for (const auto& it : rez)
		fout << it.first << " " << it.second << "\n";

	return 0;
}