#include<fstream>
#include<vector>
using namespace std;

#define NMAX 20010
#define INF 0x3f3f3f3f
const char infile[]="apm.in";
const char outfile[]="apm.out";

struct Heap
{
	int indice;
	int cheie;
	int cap;
};
Heap H[NMAX];
int poz[NMAX];

int S[NMAX*2-10];
int k=0;
vector<pair<int,int> > G[NMAX];
int N,M;
int C;
int L;

void init()
{
	for(int i=1;i<=N;i++)
	{
		poz[i]=i;
		H[i].indice=i;
		H[i].cheie=INF;
		H[i].cap=0;
	}
	H[1].cheie=0;
	L=N;
}

template<class T>
inline void schimb(T &a,T &b)
{
	T aux;
	aux=a;
	a=b;
	b=aux;
}

void urca(int i)
{
	while(i!=1 && H[i>>1].cheie>H[i].cheie)
	{
		schimb(poz[H[i>>1].indice],poz[H[i].indice]);
		schimb(H[i>>1],H[i]);
		i>>=1;
	}
}

void coboara(int i)
{
	int min;
eticheta:
	if(((i<<1)|1) <= L)
	{
		min=H[i<<1].cheie <= H[(i<<1)|1].cheie ? (i<<1):((i<<1)|1);
		if(H[i].cheie > H[min].cheie)
		{
			schimb(poz[H[i].indice],poz[H[min].indice]);
			schimb(H[i],H[min]);
			i=min;
			goto eticheta;
		}
	}
	if(i<<1 == L)
	{
		if(H[i].cheie > H[i<<1].cheie)
		{
			schimb(poz[H[i].indice],poz[H[i<<1].indice]);
			schimb(H[i],H[i<<1]);
			i<<=1;
			goto eticheta;
		}
	}
}

Heap extrage()
{
	Heap ret;
	ret=H[1];
	schimb(poz[H[1].indice],poz[H[L].indice]);
	schimb(H[1],H[L]);
	poz[H[L].indice]=0;
	L--;
	coboara(1);
	return ret;
}

void update(int i,int x,int y)
{
	H[i].cheie=x;
	H[i].cap=y;
	urca(i);
}


void citire()
{
	fstream fin(infile,ios::in);
	int x,y,c;
	fin>>N>>M;
	for(int i=1;i<=M;i++)
	{
		fin>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
		G[y].push_back(make_pair(x,c));
	}
	init();
	fin.close();
}

void afisare()
{
	fstream fout(outfile,ios::out);
	fout<<C<<"\n"<<N-1<<"\n";

	for(int i=2;i<k;i+=2)
	{
		fout<<S[i+1]<<" "<<S[i+2]<<"\n";
	}

	fout.close();
}

void proc()
{
	Heap a;
	int x;
	while(L)
	{
		a=extrage();
		
		S[k+1]=a.indice;
		S[k+2]=a.cap;
		k+=2;
		C+=a.cheie;
		x=a.indice;
		for(vector<pair<int,int> >::iterator itr=G[x].begin();itr!=G[x].end();itr++)
		{
			if(poz[itr->first])
				if(itr->second < H[poz[itr->first]].cheie)
					update(poz[itr->first],itr->second,x);
		}
	}
}

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


}