#include <fstream>
#include <vector>

#include <queue>

#define MAX_N 200005

using namespace std;

struct Vecin
{
	int vecin;
	int cost;
};

struct Muchie
{
	int i1;
	int i2;
};

int n, m;

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

vector<Vecin> vecini[MAX_N];
bool          parcursNode[MAX_N] = { false };

int finalCost;
int finalCount;

vector<pair<int, int> > results;

struct CompareFunc
{
	bool operator()(Muchie nod1, Muchie nod2)
	{
		return vecini[nod1.i1][nod1.i2].cost > vecini[nod2.i1][nod2.i2].cost;
	}
};

priority_queue<Muchie, vector<Muchie>, CompareFunc> nodeQueue;

void Prim()
{
	int crtNode = 1;
	int cost = 0;
	
	int i = 0;

	while(i <= n-1)
	{
		if (i != 0)
		{
			Muchie muchie = nodeQueue.top();
			nodeQueue.pop();

			crtNode = vecini[muchie.i1][muchie.i2].vecin;

			if (parcursNode[crtNode])
			{
				continue;
			}

			results.push_back({ muchie.i1, vecini[muchie.i1][muchie.i2].vecin });
			
			cost += vecini[muchie.i1][muchie.i2].cost;
		}

		parcursNode[crtNode] = true;

		for (int j = 0; j < vecini[crtNode].size(); j++)
		{
			if (!parcursNode[vecini[crtNode][j].vecin])
			{
				Muchie muc;

				muc.i1 = crtNode;
				muc.i2 = j;

				nodeQueue.push(muc);
			}
		}

		i++;
	}

	finalCost = cost;
	finalCount = i - 1;
}

int main(void)
{
	fin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int nod1, nod2, cost;

		fin >> nod1 >> nod2 >> cost;

		Vecin v;
		v.vecin = nod2;
		v.cost = cost;

		vecini[nod1].push_back(v);

		v.vecin = nod1;

		vecini[nod2].push_back(v);
	}

	Prim();

	fout << finalCost << endl << finalCount << endl;

	for (int i = 0; i < results.size(); i++)
	{
		fout << results[i].first << " " << results[i].second << endl;
	}

	fin.close();
	fout.close();

	return 0;
}