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

#define MAX 200001

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

vector<pair<int, int>> G[MAX];
vector<int> A[MAX];

int N, M, i, j, a, b, c, A_SIZE = 0, sum,heap_size=0;
int viz[MAX],MAP[MAX],H[MAX],POS[MAX],T[MAX];

void up(int node)
{
	while (node / 2 && H[node] <= H[node / 2])
	{
		swap(H[node], H[node / 2]);
		int a = MAP[node], b = MAP[node / 2];
		swap(MAP[node], MAP[node/2]);
		swap(POS[a], POS[b]);
		node = node / 2;
	}
}
void down(int node)
{
	int child = 0;
	do
	{
		child = 0;
		if (2 * node <= heap_size && H[2 * node] <= H[node])
			child = 2 * node;
		if (2*node +1<=heap_size)
		{
			if (!child && H[2 * node + 1] <= H[node])
				child = 2 * node + 1;
			else if (child && H[2 * node + 1] <= H[node])
				child = (H[2 * node] <= H[2 * node + 1]) ? 2 * node : 2 * node + 1;
		}
		if (child)
		{
			swap(H[node], H[child]);
			int a = MAP[node], b = MAP[child];
			swap(MAP[node], MAP[child]);
			swap(POS[a], POS[b]);
			node = child;
		}
	} while (child);
}
void insert(int val)
{
	H[++heap_size] = val;
	POS[heap_size] = heap_size;
	MAP[heap_size] = heap_size;
}
int top()
{
	return MAP[1];
}
void modify(int node,int val)
{
	H[node] = val;
	if (node / 2 && H[node] <= H[node / 2])
		up(node);
	else
		down(node);
}
void remove(int node)
{
	swap(H[heap_size], H[node]);
	int a = MAP[heap_size], b = MAP[node];
	swap(MAP[heap_size], MAP[node]);
	swap(POS[a], POS[b]);
	--heap_size;
	if (node / 2 && H[node] <= H[node / 2])
		up(node);
	else
		down(node);
}
void MST(int node)
{
	viz[1] = 1;
	for (i = 0; i < G[1].size(); ++i)
	{
		T[G[1][i].first] = 1;
		modify(POS[G[1][i].first], G[1][i].second);
	}
	int e,val;
	while (heap_size)
	{
		e = top();
		val = H[POS[e]];
		remove(1);
		if (!viz[e])
		{
			viz[e] = 1;
			A[T[e]].push_back(e);
			++A_SIZE;
			sum += val;
				for (i = 0; i < G[e].size(); ++i)
				{
					if (!viz[G[e][i].first]  && G[e][i].second<H[POS[G[e][i].first]])
					{
						T[G[e][i].first] = e;
						modify(POS[G[e][i].first], G[e][i].second);
					}
				}
		}

	}
}

int main()
{
	in >> N >> M;
	for (i = 1; i <= N; ++i)
	{
		insert(1 << 30);
	}
	for (i = 1; i <= M; ++i)
	{
		in >> a >> b >> c;
		G[a].push_back(make_pair(b, c));
		G[b].push_back(make_pair(a, c));
	}

	MST(1);
	out << sum << '\n';
	out << A_SIZE << '\n';
	for (i = 1; i <= N; ++i)
		for (j = 0; j < A[i].size(); ++j)
			out << i << " " << A[i][j] << '\n';
	return 0;
}