/*heap to know the vertexes and get min in O(1)
map to know each vertex where it is in the heap
put int the heap each vertex plus the smallest way to get to the vertex
update all the vertexes*/

#include <fstream>
#include <map>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>

using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

const int maxn = 200200;
const int INF = 9432412;

struct HEAP {
	int vertex, val;
} H[maxn], MIN;

vector<pair<int, int>> points[maxn];//points[x].first is the neighbor and points[x].second is the cost
int ANS, N, M, remaining;
map<int, int> connections;//where vertex i is in the heap :^)
map<int, pair<int, int>> SOL;

void init();
void decrease(int pos, int val);
void get_min();
void solve();
void show();

int main()
{
	init();
	solve();
	show();
	return 0;
}

void init()
{
	fi >> N >> M;
	for (int i = 1;i <= M;i++)
	{
		int x, y, z;
		fi >> x >> y >> z;
		points[x].push_back(make_pair(y, z));
		points[y].push_back(make_pair(x, z));
	}
	H[1] = { 1,0 };
	connections[1] = 1;
	for (int i = 2;i <= N;i++)
	{
		H[i].vertex = i;
		H[i].val = INF;
		connections[H[i].vertex] = i;
	}
	remaining = N;
	return;
}

void decrease(int pos, int val)
{
	H[pos].val = val;
	while (H[pos].val <= H[pos / 2].val && pos / 2 >= 1)
	{
		swap(connections[H[pos].vertex], connections[H[pos / 2].vertex]);
		swap(H[pos], H[pos / 2]);
		pos = pos / 2;
	}
	return;
}

void get_min()
{
	MIN = H[1];
	connections[H[remaining].vertex] = connections[H[1].vertex];
	connections[H[1].vertex] = INF;
	H[1] = H[remaining];
	H[remaining--] = { INF, INF };
	int pos = 1;
	while ((H[pos].val >= H[2 * pos].val || H[pos].val >= H[2 * pos + 1].val) && (2 * pos <= remaining))
	{
		if (H[pos].val >= H[2 * pos].val)
		{
			swap(connections[H[pos].vertex], connections[H[2*pos].vertex]);
			swap(H[pos], H[2*pos]);
			pos *= 2;
		}
		else if (H[pos].val >= H[2 * pos + 1].val)
		{
			swap(connections[H[pos].vertex], connections[H[2 * pos + 1].vertex]);
			swap(H[pos], H[2 * pos + 1]);
			pos *= 2;
			pos++;
		}
	}

	return;
}

void solve()
{
	int start = 0;
	while (remaining)
	{
		get_min();
		ANS += MIN.val;
		for (int i = 0;i < points[MIN.vertex].size();i++)
		{
			start = MIN.vertex;
			if (connections[points[start][i].first] != INF)
				if (points[start][i].second < H[connections[points[start][i].first]].val)
				{
					decrease(connections[points[start][i].first], points[start][i].second);
					SOL[points[start][i].first] = make_pair(start, points[start][i].first);
				}
		}
	}
	return;
}

void show()
{
	fo << ANS << "\n" << N - 1 << '\n';
	for (int i = 0; i < SOL.size();i++)
	{
		if(SOL[i].first!=SOL[i].second)
			fo << SOL[i].first << " " << SOL[i].second << "\n";
	}
	return;
}