#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];
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])
					q.push(make_pair(el, i));
		}
	}
}

int main()
{
	in >> N >> M;

	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;
}