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

struct Info
{
	int nod;
	int cost;
	bool operator()(const Info& a, const Info& b) { return a.cost > b.cost; }
};

std::vector<std::vector<Info> >la; // first = node  second = cost
int N, M;

void citire() {
	std::ifstream f("apm.in");
	f >> N >> M;
	la.resize(N + 1);

	for (int i = 0; i < M; ++i) {
		int x, y, c;
		f >> x >> y >> c;
		la[x].push_back({ y,c });
		la[y].push_back({ x,c });
	}
}

void sol() {
	std::vector<int> dist(N + 1, 1e9);
	std::vector<bool>used(N + 1, false);
	std::priority_queue<Info, std::vector<Info>, Info> pq;

	std::vector<int>parent(N + 1, -1);
	std::vector<std::pair<int, int>>muchii;
	dist[1] = 0;

	int cmin = 0;
	
	pq.push({ 1, 0 });

	while (!pq.empty()) {
		int nod = pq.top().nod;
		pq.pop();

		if (used[nod])continue;
		used[nod] = true;
		
		if(parent[nod] != -1)
			muchii.push_back({ nod, parent[nod] });

		for (auto vecin: la[nod]) {
			if (!used[vecin.nod] && vecin.cost < dist[vecin.nod]) {
				dist[vecin.nod] = vecin.cost;
				pq.push({ vecin.nod, dist[vecin.nod] });
				parent[vecin.nod] = nod;
			}
		}
	}

	for (int i = 1; i <= N; ++i)
		cmin += dist[i];

	std::ofstream g("apm.out");
	g << cmin << '\n' << muchii.size() << '\n';
	for (auto m : muchii) {
		g << m.first << ' ' << m.second << '\n';
	}
}

int main()
{
	citire();
	sol();

}