#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 4000

using namespace std;

vector<int> c;

void citire(int &n, int &m, vector<int>& x, vector<int>& y, vector<int>& indici)
{
	ifstream fin("apm.in");
	fin >> n >> m;
	int aux;
	for (int i = 0; i < m; ++i)
	{
		fin >> aux;
		x.push_back(aux);
		fin >> aux;
		y.push_back(aux);
		fin >> aux;
		c.push_back(aux);
		indici.push_back(i);
	}
	
	fin.close();
}

const bool cmp(const int &i, const int &j)
{
	return (c[i] < c[j]);
}

int grupa(const int& i, vector<int>& grup)
{
	if (grup[i] == i) 
		return i;
	grup[i] = grupa(grup[i], grup);
	return grup[i];
}

void reuniune(const int& i, const int& j, vector<int>& grup)
{
	grup[grupa(i, grup)] = grupa(j, grup);
}

void kruskal(vector<int>& grup, const vector<int>& indici, const vector<int>& x, const vector<int>& y, vector<int>& vans, const int& n, const int &m, int& ans)
{
	for (int i = 0; i < n; i++)
		grup.push_back(i);
	for (int i = 0; i < m; ++i)
	{
		if (grupa(x[indici[i]], grup) != grupa(y[indici[i]], grup))
		{
			ans += c[indici[i]];
			reuniune(x[indici[i]], y[indici[i]], grup);
			vans.push_back(indici[i]);
		}
	}
}

void afisare(const int& ans, const int& n, vector<int>& vans, const vector<int>& x, const vector<int>& y)
{
	ofstream fout("apm.out");
	fout << ans << "\n";
	fout << n-1 << "\n";
	for (int i = 0; i < n-1; ++i)
		fout << x[vans[i]] << " " << y[vans[i]] << "\n";
}

int main()
{
	int m;
	int n;
	int ans = 0;
	vector<int> grup;
	vector<int> indici;
	vector<int> x;
	vector<int> y;
	
	vector<int> vans;
	
	citire(n, m, x, y, indici);
	sort(indici.begin(), indici.end(), cmp);
	kruskal(grup, indici, x, y, vans, n, m, ans);
	afisare(ans, n, vans, x, y);
	return 0;
}