#include <fstream>
using namespace std;

#define maxn 200001
#define maxm 400001

typedef struct muchie{
	int x,y,cost;};

typedef struct graf{
	int nod,cost;
	graf *next;};

int t[maxn],n,m,nh;
graf *a[maxn];
muchie b[maxm];

void swap(int x,int y){
	int aux;
	aux=b[x].x;
	b[x].x=b[y].x;
	b[y].x=aux;
	aux=b[x].y;
	b[x].y=b[y].y;
	b[y].y=aux;
	aux=b[x].cost;
	b[x].cost=b[y].cost;
	b[y].cost=aux;}

void sift(int k){
	int son;
	do{
		son=0;
		if(k*2<=nh)
			son=k*2;
		if(k*2+1<=nh&&b[k*2].cost>b[k*2+1].cost)
			son=k*2+1;
		if(b[son].cost>b[k].cost)
			son=0;
		if(son){
			swap(son,k);
			k=son;}}
	while(son);}

void push(int k){
	while(k/2&&b[k].cost<b[k/2].cost){
		swap(k,k/2);
		k=k/2;}}

void pop(){
	swap(1,nh);
	nh--;
	sift(1);}

int root(int k){
	while(t[k]!=k)
		k=t[k];
	return k;}

void add(int nod){
	graf *q;
	q=a[nod];
	muchie k;
	while(q){
		if(root(nod)!=root(q->nod)){
		k.x=nod;
		k.y=q->nod;
		k.cost=q->cost;
		nh++;
		b[nh]=k;
		push(nh);}
		q=q->next;}}

int main(){
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	int nod,i,x,y,z,c=0;
	muchie min;
	graf *q;
	for(i=1;i<=m;i++){
		f>>x>>y>>z;
		q=new graf;
		q->nod=y;
		q->cost=z;
		q->next=a[x];
		a[x]=q;
		q=new graf;
		q->nod=x;
		q->cost=z;
		q->next=a[y];
		a[y]=q;}
	t[1]=1;
	add(1);
	while(nh){
		min=b[1];
		pop();
		if(root(min.x)!=root(min.y)){
			c=c+min.cost;
			if(root(min.x)==1){
				t[min.y]=min.x;
				nod=min.y;}
			else {
				t[min.x]=min.y;
				nod=min.x;}
			add(nod);}}
	g<<c<<"\n"<<n-1<<"\n";
	for(i=2;i<=n;i++)
		g<<i<<" "<<t[i]<<"\n";
	f.close();
	g.close();
	return 0;}