#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <tuple>
using namespace std;

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

const int Inf = 0x3f3f3f3f,
		  MaxN = 200001;

struct Edge {
	Edge() : node {0}, key{0}
	{}
	Edge(int node, int key) :
		node {node}, key{key}
	{}

	bool operator < (const Edge& e) const
	{
		return key > e.key;
	}

	int node, key;
};

using VI  = vector<int>;
using VP  = vector<pair<int, int>>;
using VVP = vector<VP>;

int N;
VVP G;   // graful
VI key;  // cheile asociate nodurilor
VI t;    // sirul de "tati" (retine APM)
bitset<MaxN> v; // marcheaza cu 1 nodurile
                // aflate in APM (cele care ies din coada)
VP apm;  // retine muchiile APM-ului
long long cost_apm;


void ReadGraph();
void Prim(int x);
void WriteAPM();

int main()
{
	ReadGraph();
	Prim(1);

	WriteAPM();
}

void ReadGraph()
{
	int X, Y, C, M;

	fin >> N >> M;
	G = VVP(N + 1);

	while (M--)
	{
		fin >> X >> Y >> C;
		G[X].emplace_back(Y, C);
		G[Y].emplace_back(X, C);
	}
}

void Prim(int x)
{
	priority_queue<Edge> Q;
	t = VI(N + 1);
	key = VI(N + 1, Inf);
	key[x] = 0;
	Q.emplace(x, 0);

	int y, w; // ky = ponderea muchiei de la x la y
	while (!Q.empty())
	{
		x = Q.top().node;
		v[x] = 1; // marcam ca x se adauga in APM
		for (auto& p : G[x])
		{
			tie(y, w) = p;

			if (v[y]) continue;
			if (key[y] > w)
			{
				key[y] = w;
				t[y] = x;
				Q.emplace(y, key[y]);
			}
		}

		apm.emplace_back(x, t[x]);
		cost_apm += key[x];

		while (!Q.empty() && v[Q.top().node])
			Q.pop();
	}
}

void WriteAPM()
{
	fout << cost_apm << '\n';

	fout << apm.size() - 1 << '\n';

	for (size_t i = 1; i < apm.size(); ++i)
		fout << apm[i].first << ' ' << apm[i].second << '\n';

}