#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define NMax 200001
#define inf 2000000000
using namespace std;

struct Nod{int ext,cost;};
struct Heap{int val,nod;};

Nod *A[NMax];
Heap cmin[NMax];
int n,m,start=1,pred[NMax],Hpoz[NMax],N;

inline int father(int k) { return k/2;}
inline int left_son(int k) { return 2*k;}
inline int right_son(int k) { return 2*k+1;}

void UpHeap(int nod)
{
	while(nod>1&&cmin[father(nod)].val>cmin[nod].val)
	{
		swap(Hpoz[cmin[nod].nod],Hpoz[cmin[father(nod)].nod]);
		swap(cmin[nod],cmin[father(nod)]);
		nod=father(nod);
	}
}

void DownHeap(int nod)
{
	int son;
	do
	{
		son=0;
		if(left_son(nod)<=N)
		{
			son=left_son(nod);
			if(right_son(nod)<=N&&cmin[son].val>cmin[right_son(nod)].val)
				son=right_son(nod);
			if(cmin[son].val>cmin[nod].val) son=0;
		}
		if(son)
		{
			swap(Hpoz[cmin[nod].nod],Hpoz[cmin[son].nod]);
			swap(cmin[son],cmin[nod]);
			nod=son;
		}
	}while(son);
}

void BuildHeap()
{
	int i;
	for(i=n/2;i>0;i--)
		DownHeap(i);
}

Heap ExtractMin()
{
	Heap Min=cmin[1];
	swap(Hpoz[cmin[1].nod],Hpoz[cmin[N].nod]);
	swap(cmin[1],cmin[N]);
	--N;
	DownHeap(1);
	return Min;
}

void Citire()
{
	FILE *fin=fopen("apm.in","r");
	int i,a,b,c;
	fscanf(fin,"%d %d",&n,&m);
	N=n;
	for(i=1;i<=n;++i)
		A[i]=(Nod*)realloc(A[i],sizeof(Nod)),A[i][0].ext=0;
	while(m--)
	{
		fscanf(fin,"%d%d%d",&a,&b,&c);
		A[a][0].ext++;
		A[a]=(Nod*)realloc(A[a],(A[a][0].ext+1)*sizeof(Nod));
		A[a][A[a][0].ext].ext=b;
		A[a][A[a][0].ext].cost=c;

		A[b][0].ext++;
		A[b]=(Nod*)realloc(A[b],(A[b][0].ext+1)*sizeof(Nod));
		A[b][A[b][0].ext].ext=a;
		A[b][A[b][0].ext].cost=c;
	}
	for(i=1;i<=n;++i)
		cmin[i].nod=i,cmin[i].val=inf,Hpoz[i]=i;
	for(i=1;i<=A[start][0].ext;++i)
	{
		cmin[A[start][i].ext].val=A[start][i].cost;
		pred[A[start][i].ext]=start;
	}
	cmin[start].val=-1001;
	BuildHeap();
	ExtractMin();
}

void Update(int nod_in_heap)
{
	if(nod_in_heap>1&&cmin[father(nod_in_heap)].val>cmin[nod_in_heap].val)
		UpHeap(nod_in_heap);
		else DownHeap(nod_in_heap);
}

void Prim()
{
	int i,nrVf=n-1,VfMin,ValMin;
	Heap Min;
	while(nrVf--)
	{
		Min=ExtractMin();
		VfMin=Min.nod;
		ValMin=Min.val;
		for(i=1;i<=A[VfMin][0].ext;i++)
			if(Hpoz[A[VfMin][i].ext]<=N&&A[VfMin][i].cost<cmin[Hpoz[A[VfMin][i].ext]].val)
			{
				cmin[Hpoz[A[VfMin][i].ext]].val=A[VfMin][i].cost;
				pred[A[VfMin][i].ext]=VfMin;
				Update(Hpoz[A[VfMin][i].ext]);
			}
	}
}

void Afisare()
{
	FILE *fout=fopen("apm.out","w");
	int CostAmP=0,i,j;
	for(i=1;i<=n;i++)
		if(i!=start)
		for(j=1;j<=A[i][0].ext;j++)
		{
			if(A[i][j].ext==pred[i])
			{
				CostAmP+=A[i][j].cost;
				break;
			}
		}
	fprintf(fout,"%d\n%d\n",CostAmP,n-1);
	for(i=1;i<=n;i++)
		if(i!=start)
			fprintf(fout,"%d %d\n",i,pred[i]);

}

int main()
{
	Citire();
	Prim();
	Afisare();
	return 0;
}