#include <fstream> 
#include <vector>

#define NMAX 50001
#define MMAX 50001


using namespace std;

//Variabile Globale:
int N,M;
vector<pair<int,int> > G[NMAX];

struct heap
{
	int start;
	int end;
	int cost;
};

heap H[2*MMAX];
heap Z[NMAX];

int Cost,Lung,S;
short is[NMAX];


//Swap:
void swap(heap &a,heap &b)
{
	heap aux;
	aux=a;
	a=b;
	b=aux;
}

//Urca:
void push_up(int l)
{
	while(l!=1 && H[l].cost<H[l/2].cost)
	{
		swap(H[l],H[l/2]);
		l/=2;
	}
}

//Coboara:
void push_down(int l)
{
	eticheta:
	
	if(2*l+1<=Lung)
	{
		if(H[2*l].cost<=H[2*l+1].cost)
		{
			if(H[2*l].cost <H[l].cost)
			{
				swap(H[2*l],H[l]);
				l=2*l;
				goto eticheta;
			}
		}
		else if(H[2*l].cost>=H[2*l+1].cost)
		{
			if(H[2*l+1].cost<H[l].cost)
			{
				swap(H[2*l+1],H[l]);
				l=2*l+1;
				goto eticheta;
			}
		}
	}
	else if(2*l==Lung)
	{
		if(H[l].cost>H[2*l].cost)
		{
			swap(H[l],H[2*l]);
		}
		
	}
}

//Citire:
void citire()
{
	fstream fin("apm.in",ios::in);
	fin>>N>>M;
	int x,y,c;
	for(register 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));
	}
	fin.close();
}

//Afisare:
void afisare()
{
	fstream fout("apm.out",ios::out);
	
	fout<<Cost<<"\n";
	fout<<N-1<<"\n";
	for(int i=1;i<=N-1;i++)
	{
		fout<<Z[i].start<<" "<<Z[i].end<<"\n";
	}
	
	fout.close();
}
//Add:
void add(int x)
{
	for(vector<pair<int,int> >::iterator itr=G[x].begin();itr!=G[x].end();itr++)
	{
		if(!is[itr->first])
		{
			heap aux;
			aux.start=x;
			aux.end=itr->first;
			aux.cost=itr->second;
			Lung++;
			H[Lung]=aux;
			push_up(Lung);
		}
	}
}
//Extrage min :
int extrage(heap &x)
{
	int ret;
	if(Lung)
	{
		x=H[1];
		swap(H[1],H[Lung]);
		ret=1;
		H[Lung].cost=0;
		H[Lung].start=0;
		H[Lung].end=0;
		Lung--;
		push_down(1);
	}
	else ret=0;
	return ret;
}


//Initializari:
void init()
{
	S++;
	is[1]++;
	add(1);
}

//Prim:
void prim()
{
	int z=1;
	heap x;
	int ok=0;
	while(S!=N)
	{
		while(!ok)
		{
			extrage(x);
			if(!is[x.end]) 
			{
				ok++;
				is[x.end]++;
			}
		}
		ok=0;
		S++;
		Z[z++]=x;
		Cost+=x.cost;
		
		add(x.end);
	}
}

//Main:
int main(int argc, char* argv[])
{
	citire();

	init();
	
	prim();

	afisare();
}