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

using namespace std;

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

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	int n, m;
	f >> n >> m;
	int a, b, c;
	for (int 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);
	}
	viz[1] = 1;
	int lim = graph[1].size();
	for (int i = 0; i < lim; i++)
	{
		int vecin = graph[1][i];
		int cost = graphC[1][i];
		myheap.push(make_pair(-cost, make_pair(1, vecin)));
	}
	int costm = 0;
	int muchii = 0;
	while (!myheap.empty())
	{
		pair<int, pair<int, int> > best = myheap.top();
		myheap.pop();
		int index = best.second.second;
		if (viz[index])
			continue;
		viz[index] = 1;
		apm.push_back(best.second);
		muchii++;
		costm = costm - best.first;
		int lim = graph[index].size();
		for (int i = 0; i < lim; i++)
		{
			int vecin = graph[index][i];
			int cost = graph[index][i];
			myheap.push(make_pair(-cost, make_pair(index, vecin)));
		}
	}
	g << costm << "\n";
	g << muchii << "\n";
	for (int i = 0; i < muchii; i++)
		g << apm[i].first << " " << apm[i].second << "\n";
	return 0;
}