/* Algoritmul lui Prim
 * Determina APM astfel:
 * Asociaza fiecarui nod x, o cheie key[x], avand semnificatia
 * ca este costul minim al unei muchii incidente cu x
 * si cu un nod din APM.
 * APM porneste de la un nod de start (de ex 1), avand cheia 0.
 * Sirul key se initializeaza cu Infinit.
 * Pentru fiecare muchie avand un capat in arbore si celalalt
 * capat in graf, se alege "muchia usoara", adica de pondere minima.
 * Iar nodul din graf se adauga la APM.
 */
#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 a, b, w, m;

	fin >> n >> m;
	G = VVP(n + 1);

	while (m--)
	{
		fin >> a >> b >> w;
		G[a].emplace_back(b, w);
		G[b].emplace_back(a, w);
	}
}

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';

}