#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

priority_queue <pair<int, pair<int, int> > > myqueue;
vector <int> graph[100005];
vector <int> graphC[100005];
vector <pair<int, int> > apm;
int viz[100005];

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	int n, m;
	f >> n >> m;
	int i;
	int a, b, c;
	for (i = 1; i <= m; i++)
	{
		f >> a >> b >> c;
		graph[a].push_back(b);
		graphC[a].push_back(c);
		graph[b].push_back(a);
		graphC[b].push_back(c);
	}
	int lim;
	lim = graph[1].size();
	viz[1] = 1;
	for (i = 0; i < lim; i++)
	{
		int vecin = graph[1][i];
		int cost = graphC[1][i];
		myqueue.push(make_pair(-cost, make_pair(1, vecin)));

	}
	int muchii=0, costG=0;
	while (!myqueue.empty())
	{
		pair<int,pair<int,int> > best = myqueue.top();
		int index = best.second.second;
		myqueue.pop();
		if (viz[index])
			continue;
		viz[index] = 1;
		muchii++;
		costG = costG - best.first;
		apm.push_back(best.second);
		lim = graph[index].size();
		for (i = 0; i < lim; i++)
		{
			int vecin = graph[index][i];
			int cost = graphC[index][i];
			myqueue.push(make_pair(-cost, make_pair(index, vecin)));
		}
	}
	g << costG << "\n";
	g << muchii << "\n";
	for (i = 0; i < muchii; i++)
		g << apm[i].first << " " << apm[i].second << "\n";
	return 0;
}