#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

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

const int Inf = 0x3f3f3f3f;
const int MaxN = 200002;

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

	int node, key;
};

using VI  = std::vector<int>;
using VE  = std::vector<Edge>;
using VVE = std::vector<VE>;

int n;
std::bitset<MaxN> v;

VVE G;
VE apm;
VI key;
VI t;
long long costApm;

void Read();
void Prim(int x);
void Write();

int main()
{
	Read();
	Prim(1);
	Write();

	return 0;
}

void Read()
{
	int x = 0, y = 0, c = 0, m = 0;

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

	while (m--)
	{
		fin >> x >> y >> c;
		G[x].push_back({ y, c });
		G[y].push_back({ x, c });
	}
}

void Prim(int x)
{
	std::priority_queue<Edge> Q;
	key = VI(n + 1, Inf);
	t = VI(n + 1);

	int y = 0, c = 0;
	key[x] = 0;
	Q.push({ x, 0 });

	while (!Q.empty())
	{
	    x = Q.top().node;
		v[x] = 1;

		for (auto& p : G[x])
		{
		    y = p.node;
		    c = p.key;

			if (v[y]) continue;

			if (key[y] > c)
			{
				key[y] = c;
				t[y] = x;
				Q.push({ y, key[y] });
			}
		}

		apm.push_back({ x, t[x] });
		costApm += key[x];

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

void Write()
{
	fout << costApm << '\n';
	fout << apm.size() - 1 << '\n';

	for (size_t i = 1; i < apm.size(); ++i)
        fout << apm[i].node << ' ' << apm[i].key << '\n';
}