#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
using namespace std;

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

int N, M;
map<int, vector<pair<int, int>>> G;
map<int, int> dist, father;
map<int, bool> visited;

int total = 0;
vector<pair<int, int>> sol;

const int INF = 1 << 30;

void Prim()
{
	for (int i = 1; i <= N; i++)
		dist[i] = INF, father[i] = 1, visited[i] = false;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;
	
	queue.push({ 0, 1 });
	while (!queue.empty())
	{
		int node = queue.top().second;
		int cost = queue.top().first;
		queue.pop();

		if (dist[node] < cost)
			continue;

		visited[node] = true;

		total += cost;
		if (node != 1)
			sol.push_back({ father[node],node });

		for (auto child : G[node])
		{
			int next = child.first;
			int c = child.second;

			if (!visited[next] && dist[next] > c)
			{
				dist[next] = c;
				father[next] = node;
				queue.push({ c, next });
			}
		}
	}
}

int main()
{
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int x, y, c;
		fin >> x >> y >> c;
		G[x].push_back({ y, c });
		G[y].push_back({ x, c });
	}

	Prim();

	fout << total << "\n";
	fout << sol.size() << "\n";
	for (auto s : sol)
		fout << s.first << " " << s.second << "\n";

	return 0;
}