#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int Nmax = 200005;
const int Mmax = 400005;

struct Edge {
	int x,y,c,g;
}; 

int N,M;
Edge edges[Mmax];
int disjoint[Nmax];
int sol = 0;

int findHead(int a)
{
	if (!disjoint[a])
		return a;
	int head=a;
	while (disjoint[head] != 0) 
		head = disjoint[head];
	disjoint[a] = head;
	return head;
}

int areDisjoint(int a,int b)
{
	int heada = a,headb = b;
	for(; disjoint[heada] ; heada = disjoint[heada]);
	for(; disjoint[headb] ; headb = disjoint[headb]);
	if (heada == headb)
		return 0;
	return 1;
}

void unite(int a,int b)
{
	int heada = a,headb = b,aux,auxheada;
	for(; disjoint[heada] ; heada = disjoint[heada]);

	auxheada = a;
	while (disjoint[auxheada])
	{
		aux = disjoint[auxheada];
		disjoint[auxheada] = heada;
		auxheada = aux;
	}
	while (disjoint[headb])
	{
		aux = disjoint[headb];
		disjoint[headb] = heada;
		headb = aux;
	}
	disjoint[headb] = heada;
}

void solve()
{
	for(int j=0;(unsigned int)j < M; ++j)
		if (areDisjoint( edges[j].x , edges[j].y ))
		{
			unite( edges[j].x , edges[j].y );
			sol += edges[j].c;
			edges[j].g = 1;
		}
}

bool cmp(Edge e1,Edge e2)
{
	return (e1.c < e2.c);
}

void sortV()
{
	sort(edges+0,edges+M,cmp);
}

void readV()
{
	int a,b,c;
	ifstream fin;

	fin.open("apm.in");
	fin >> N;
	fin >> M;
	for(int i=0;i<M;++i)
	{
		fin >> edges[i].x >> edges[i].y >> edges[i].c;
		edges[i].g = 0;
	}
}

void printSol()
{
	ofstream fout;
	fout.open("apm.out");
	fout << sol << endl;
	fout << N-1 << endl;
	for(int i=0;(unsigned int)i < M;++i)
		if (edges[i].g)
			fout << edges[i].x << " " << edges[i].y << endl;
	fout.close();
}

int main()
{
	readV();
	sortV();
	solve();
	printSol();
	return 0;
}