#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define Infinit INT_MAX
#define Nmax 200003
using namespace std;

///------FISIERE-------
ifstream f("apm.in");
ofstream g("apm.out");
int viz[Nmax];
vector< pair <int, int> > graph[Nmax], muchii;
priority_queue < pair <int, pair<int, int> > > HEAP;

int main()
{
    int N, M, X, Y, C, cost = 0;
	f >> N >> M;

	for (int i = 0; i < M; i++)
	{
		f >> X >> Y >> C;
		graph[X].push_back(make_pair(C, Y));
		graph[Y].push_back(make_pair(C, X));
	}
	viz[1] = 1;
    int lim =(int)graph[1].size();
	for (int i = 0; i < lim; i++)
	{   //iau muchiile incidente cu nodul 1
		pair<int, int> aux = graph[1][i];
		pair<int, pair<int, int> > muchie = make_pair(-aux.first, make_pair(1, aux.second));
		HEAP.push(muchie);
	}

	while (HEAP.empty() == 0)
	{
		pair<int, pair<int, int> > minim = HEAP.top();
		HEAP.pop();
		int index = minim.second.second;

		if (viz[index] == 0)
		{
			viz[index] = 1;
			cost = cost + (-1) * minim.first;
			muchii.push_back(minim.second);
            lim = (int)graph[index].size();
			for (int i = 0; i < lim; i++)
				if (viz[graph[index][i].second] == 0)
				{
					pair<int, pair<int, int> > muchie = make_pair(-graph[index][i].first, make_pair(index, graph[index][i].second));
					HEAP.push(muchie);
				}
		}
	}

	g << cost << endl << N - 1 << endl;
	for (int i = 0; i < N - 1; i++)
		g << muchii[i].first << " " << muchii[i].second << endl;

	return 0;
}