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

using namespace std;

const int Nmax = 200005;
const int Mmax = 400005;
const int inf = 0x3f3f3f3f;

int N,M;
vector< pair< pair<int,int> ,int> > L;
int disjoint[Nmax];

vector< pair< pair<int,int> ,int> > res;
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;
	for(; disjoint[heada] ; heada = disjoint[heada]);
	while (disjoint[headb])
	{
		aux = disjoint[headb];
		disjoint[headb] = heada;
		headb = aux;
	}
	disjoint[headb] = heada;
}

void solve()
{
	int j=0;
	for(int i=1;i<N;++i)
	{
		int ok = 1;
		for(;(unsigned int)j < L.size() && ok; ++j)
			if (areDisjoint( L[j].first.first , L[j].first.second ))
			{
				unite( L[j].first.first , L[j].first.second );
				sol += L[j].second;
				res.push_back( L[j] );
				ok = 0;
			}
	}
}

bool cmp(pair< pair<int,int> ,int> it1,pair< pair<int,int> ,int> it2)
{
	return (it1.second < it2.second);
}

void sortV()
{
	sort(L.begin(),L.end(),cmp);
}

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

	fin.open("apm.in");
	fin >> N;
	fin >> M;
	for(int i=1;i<=M;++i)
	{
		fin >> a >> b >> c;
		L.push_back( make_pair(make_pair(a,b),c) );
	}
}

void printSol()
{
	ofstream fout;
	fout.open("apm.out");
	fout << sol << endl;
	fout << N-1 << endl;
	for(int i=0;(unsigned int)i < res.size();++i)
		fout << res[i].first.first << " " << res[i].first.second << endl;
	fout.close();
}

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