/*
 *Algoritmul lui Prim
 */
#include<cstdio>
const int MAXN=200010;
const int INF=200000000;
struct list_node
{
	int dest,cost;
	list_node* next;
};
typedef list_node* list;
list adj[MAXN];
int n,m,heapsize;
int h[MAXN],d[MAXN],poz[MAXN],src[MAXN];

int parent(int i){return (i>>1);}
int left(int i){return (i<<1);}
int right(int i){return ((i<<1)+1);}

void swap(int& a,int& b);
void up_heap(int i);
void down_heap(int i);
int extract_min();
void addEdge(int u,int v,int w);
void clear();
void apm_prim();
void read();
void write();

int main()
{
	read();
	apm_prim();
	write();
	clear();
	return 0;
}
void swap(int& a,int& b)
{
	a=a+b;
	b=a-b;
	a=a-b;
}
void up_heap(int i)
{
	int son,father;
	while (i>1)
	{
		son=h[i];
		father=h[parent(i)];
		if (d[son]<d[father])
		{
			swap(h[i],h[parent(i)]);
			swap(poz[son],poz[father]);
			i>>=1;
		}
		else
			break;
	}
}
void down_heap(int i)
{
	int l=left(i),r=right(i),smallest=i;
	if (l<=heapsize && d[h[l]]<d[h[smallest]])
		smallest=l;
	if (r<=heapsize && d[h[r]]<d[h[smallest]])
		smallest=r;
	if (smallest!=i)
	{
		int father=h[i],son=h[smallest];
		swap(h[i],h[smallest]);
		swap(poz[son],poz[father]);
		down_heap(smallest);
	}
}

int extract_min()
{
	int top=h[1],bottom=h[heapsize];

	swap(poz[top],poz[bottom]);
	swap(h[1],h[heapsize]);

	poz[h[heapsize]]=-1;
	h[heapsize--]=0;
	down_heap(1);
	return top;
}
void addEdge(int u,int v,int w)
{
	list_node *p,*q;
	/* Insert u->v */
	q=adj[u];	p=new list_node();
	p->dest=v;	p->cost=w;	p->next=q;
	adj[u]=p;
	/* Insert v->u */
	q=adj[v];	p=new list_node();
	p->dest=u;	p->cost=w;	p->next=q;
	adj[v]=p;
}
void clear()
{
	list_node *p;
	for (int i=1; i<=n; ++i)
	{
		while (adj[i] && adj[i]->next)
		{
			p=adj[i]->next;
			delete adj[i];
			adj[i]=NULL;
			adj[i]=p;
		}
		delete adj[i];
	}
}



void apm_prim()
{
	/* INITIALIZARE */
	int i,u;
	heapsize=n;
	for (i=1; i<=n; ++i)
	{
		d[i]=INF;
		poz[i]=h[i]=i;
	}
	d[1]=0;
	/* TRAVESARE */
	while (heapsize)
	{
		u=extract_min();
		for (list_node *p=adj[u]; p!=NULL; p=p->next)
		{
			int v=p->dest,w=p->cost;
			if (d[v]>w && poz[v]!=-1)
			{
				src[v]=u;
				d[v]=w;
				up_heap(poz[v]);
			}
		}
	}
}
void read()
{
	int i,u,v,w;
	FILE *fin=fopen("apm.in","r");
	fscanf(fin,"%d%d",&n,&m);
	for (i=1; i<=m; ++i)
	{
		fscanf(fin,"%d%d%d",&u,&v,&w);
		addEdge(u,v,w);
	}
	fclose(fin);
}
void write()
{
	int sum=0;
	FILE *fout=fopen("apm.out","w");
	for (int i=2; i<=n; ++i)
		sum+=d[i];
	fprintf(fout,"%d\n%d\n",sum,n-1);
	for (int i=2; i<=n; ++i)
	{
		fprintf(fout,"%d %d\n",src[i],i);
	}
	fclose(fout);
}