#include <fstream>
#include <algorithm>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;

const int MAXN = 200005;

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

int N, M;
int H[2 * MAXN + 100], L, Poz[MAXN], D[MAXN], T[MAXN];
int costAPM;
vector < pair <int, int> > G[MAXN], Arb;

int Father(int node)
{
	return node >> 1;
}

int LeftSon(int node)
{
	return node << 1;
}

int RightSon(int node)
{
	return (node << 1) + 1;
}

void ReadData()
{
	fin >> N >> M;
	for (int i = 1; i <= M; ++i)
	{
		int a, b, c;
		fin >> a >> b >> c;
		G[a].push_back( make_pair(b, c) );
		G[b].push_back( make_pair(a, c) );
	}
	for (int i = 2; i <= N; ++i)
		D[i] = INF;
}

void Insert_in_APM(int node)
{
	for (int i = 0; i < G[node].size(); ++i)
	{
		int vecin = G[node][i].first;
		int cost = G[node][i].second;
		D[vecin] = min(D[vecin], cost);
		if (D[vecin] == cost)
			T[vecin] = node;
	}
}

void Percolate(int node)
{
	while (node > 1 && D[ H[node] ] < D[ H[Father(node)] ])
	{
		swap(H[node], H[Father(node)]);
		swap(Poz[ H[node] ], Poz[ H[Father(node)] ]);
		node = Father(node);
	}
}

void Sift(int node)
{
	int son;
	do
	{
		son = 0;
		if (LeftSon(node) <= L)
		{
			son = LeftSon(node);
			if (RightSon(node) <= L && D[ H[RightSon(node)] ] < D[ H[LeftSon(node)] ] )
				son = RightSon(node);
			if (D[ H[son] ] > D[ H[node] ]) son = 0;
		}
		if (son)
		{
			swap(H[son], H[node]);
			swap(Poz[ H[son] ], Poz[H [node] ]);
			node = son;
		}
	} while (son);
}

void Insert_in_Heap(int node)
{
	H[++L] = node;
	Poz[node] = L;
	Percolate(L);
}

int Extract_Root()
{
	int R = H[1];
	swap(H[1], H[L]);
	swap(Poz[ H[1] ], Poz[ H[L] ]);
	--L;
	Sift(1);
	Poz[R] = 0;
	return R;
}

void Prim()
{
	Insert_in_APM(1);
	for (int i = 2; i <= N; ++i) Insert_in_Heap(i);
	for (int i = 1; i < N; ++i)
	{
		int R = Extract_Root();
		Insert_in_APM(R);
		costAPM += D[R];
		Arb.push_back( make_pair(R, T[R]) );
		for (int j = 0; j < G[R].size(); ++j)
		{
			int vecin = G[R][j].first;
			if (Poz[vecin]) Percolate(Poz[vecin]);
		}
	}
}

void WriteData()
{
	fout << costAPM << '\n';
	fout << N - 1 << '\n';
	for (int i = 0; i < N - 1; ++i)
		fout << Arb[i].first << " " << Arb[i].second << '\n';
}

int main()
{
	ReadData();
	Prim();
	WriteData();
	fin.close();
	fout.close();
	return 0;
}