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

using namespace std;

const int NMAX = 200001,
          INF = 1 << 10;

struct muchie
{
	int y, w;

	muchie(int yy = 0, int ww = 0): y(yy), w(ww) {}

	bool operator<(const muchie &m) const
	{
		return w > m.w;
	}
};

int N, M, COST,
    D[NMAX], T[NMAX];

priority_queue<muchie> Q;
vector<muchie> G[NMAX];
vector<pair<int, int>> sol;

bool viz[NMAX];

void citire()
{
	ifstream f("apm.in");
	int x, y, cost;
	f >> N >> M;
	for(int i = 1; i <= M; i++)
	{
		f >> x >> y >> cost;
		G[x].push_back(muchie(y, cost));
		G[y].push_back(muchie(x, cost));
	}
	f.close();
}

void Prim()
{
	for(int i = 2; i <= N; i++)
		D[i] = INF;
	Q.push(muchie(1, 0));
	//
	while(!Q.empty())
	{
		auto crt = Q.top();
		Q.pop();
		//
		if(viz[crt.y]) continue;
		viz[crt.y] = 1;
		//
		COST += D[crt.y];
		//
		if(T[crt.y])
			sol.push_back({crt.y, T[crt.y]});
		for(const auto &m : G[crt.y])
			if(m.w < D[m.y] && !viz[m.y])
			{
				T[m.y] = crt.y;
				D[m.y] = m.w;
				Q.push(m);
			}
	}
}

void afisare()
{
	ofstream g("apm.out");
	g << COST << '\n' << sol.size() << '\n';
	for(const auto &x : sol)
		g << x.first << ' ' << x.second << '\n';
	g.close();
}

int main()
{
	citire();
	Prim();
	afisare();
	return 0;
}