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

using namespace std;


const string file = "apm";

const string infile = file + ".in";
const string outfile = file + ".out";


struct GNod
{
	int y;
	int c;

	GNod(int y, int c)
	{
		this->y = y;
		this->c = c;
	}
};

#define NMAX 200002
#define INF 1<<30
vector<GNod> G[NMAX];


int N;
int M;
int Cost = 0;
bool viz[NMAX];
int d[NMAX];
int prec[NMAX];
queue<int> solution;


int heap[NMAX];
int heapSize;
int heapPoz[NMAX];


inline int parrent(int l)
{
	return l >> 1;
}

inline int leftSon(int l)
{
	return (l << 1);
}

inline int rightSon(int l)
{
	return (l << 1) + 1;
}

void swapHeap(int a, int b)
{
	int aux = heap[a];
	heap[a] = heap[b];
	heap[b] = aux;

	heapPoz[heap[a]] = a;
	heapPoz[heap[b]] = b;
}


void upHeap(int l)
{
	if( l == 1)
		return;

	int p = parrent(l);
	if(d[heap[p]] > d[heap[l]])
	{
		swapHeap(p, l);
		upHeap(p);
	}

}

void downHeap(int l)
{
	int left = leftSon(l);
	int right = rightSon(l);

	int minim = l;

	if(left <= heapSize && d[heap[minim]] > d[heap[left]])
	{
		minim = left;
	}
	if(right <= heapSize && d[heap[minim]] > d[heap[right]])
	{
		minim = right;
	}

	if(minim != l)
	{
		swapHeap(l, minim);
		downHeap(minim);
	}


}



int topHeap()
{
	return heap[1];
}

void insertHeap(int value)
{
	heapSize++;
	heap[heapSize] = value;
	heapPoz[value] = heapSize;
	upHeap(heapSize);
}

void popHeap()
{
	swapHeap(1, heapSize);

	heapSize--;
	downHeap(1);
}



void solve()
{

	for(int i = 2; i <= N; i++)
	{
		d[i] = INF;
	}

	insertHeap(1);
	int current;
	while(heapSize != 0)
	{
		
		current = topHeap();
		popHeap();

		viz[current] = true;


		solution.push(current);
		solution.push(prec[current]);


		Cost+= d[current];

		for(vector<GNod>::iterator itr = G[current].begin();
			itr != G[current].end();
			itr++)
		{
			int first = itr->y;
			int second = itr->c;

			if(viz[itr->y])
				continue;

			if(d[itr->y] > itr->c)
			{
				d[itr->y] = itr->c;
				prec[itr->y] = current;
				if(heapPoz[itr->y] == 0)
				{
					insertHeap(itr->y);
				}
				else
				{
					upHeap(heapPoz[itr->y]);
				}

			}
		}

	}
}

void citire()
{
	fstream fin(infile.c_str(), ios::in);

	fin >> N >> M;


	for(int i = 0; i < M ; i++)
	{
		int x, y, c;

		fin >> x >> y >> c;


		G[x].push_back(GNod(y, c));
		G[y].push_back(GNod(x, c));

	}



	fin.close();
}



void afisare()
{
	fstream fout(outfile.c_str(), ios::out);

	fout << Cost << "\n";
	fout << N - 1 << "\n";

	solution.pop();
	solution.pop();

	while(solution.empty() == false)
	{
		fout << solution.front() << " ";
		solution.pop();
		fout << solution.front() << "\n";
		solution.pop();
	}


	fout.close();
}

int main()
{
	citire();
	solve();
	afisare();

}