#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];
struct compare
{
	bool operator()(const pair<int, int> &l, const pair<int, int>& r)
	{
		return G[l.first][l.second].second > G[r.first][r.second].second;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, compare> q;

int N, M, i, j, a, b, c, A_SIZE = 0, sum;
int viz[MAX],D[MAX];
void MST(int node)
{
	q.push(make_pair(0, node));
	pair<int, int> p;
	int el;
	while (q.size())
	{
		p = q.top();
		q.pop();
		if (p.first)
			el = G[p.first][p.second].first;
		else
			el = p.second;

		if (!viz[el])
		{
			if (p.first)
			{
				A[p.first].push_back(el);
				++A_SIZE;
			}
			viz[el] = 1;
			if (p.first)
				sum += G[p.first][p.second].second;
			for (i = 0; i < G[el].size(); ++i)
				if (!viz[G[el][i].first] && G[el][i].second <= D[G[el][i].first])
					q.push(make_pair(el, i)), D[G[el][i].first] = G[el][i].second;
		}
	}
}

int main()
{
	in >> N >> M;
	for (i = 1; i <= N; ++i)
		D[i] = (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;
}