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

#define N_MAX 200010

typedef pair <int,int> p;

vector <p> a[N_MAX];
vector <p> ::iterator it;

int heap[N_MAX],poz[N_MAX];
int tata[N_MAX],cost[N_MAX];
int dimHeap;
bool ut[N_MAX],inHeap[N_MAX];

int n,m,i,j,x,y,z;
int sol;

void upHeap(int x)
{
	while(1<x&&cost[ heap[x>>1] ]>cost[ heap[x] ])
	{
		swap(poz[ heap[x>>1] ],poz[ heap[x] ]);
		swap(heap[x>>1],heap[x]);
		x=x>>1;
	}
}

void downHeap(int x)
{
	int st=x<<1;
	int dr=(x<<1)+1;
	int minim=x;
	
	if(st<=dimHeap&&cost[ heap[st] ]<cost[ heap[minim] ])
		minim=st;
	if(dr<=dimHeap&&cost[ heap[dr] ]<cost[ heap[minim] ])
		minim=dr;
	
	if(minim!=x)
	{
		swap(poz[ heap[x] ],poz[ heap[minim] ]);
		swap(heap[x],heap[minim]);
		downHeap(minim);
	}
}

void sterge(int x)
{
	swap(poz[ heap[x] ],poz[ heap[dimHeap] ]);
	swap(heap[x],heap[dimHeap]);
	
	dimHeap--;
	
	if(1<x&&cost[ heap[x>>1] ]>cost[ heap[x] ])
		upHeap(x);
	else
		downHeap(x);
}

void adauga(int nod)
{
	heap[++dimHeap]=nod;
	poz[nod]=dimHeap;
	
	upHeap(dimHeap);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		
		a[x].push_back(p(y,z));
		a[y].push_back(p(x,z));
	}
	
	for(i=2;i<=n;i++)
	{
		cost[i]=(1<<30);
		adauga(i);
	}
	
	ut[1]=1;
	for(it=a[1].begin();it!=a[1].end();it++)
	{
		cost[it->first]=it->second;
		tata[it->first]=1;
		
		upHeap(poz[it->first]);
	}
	
	for(i=1;i<n;i++)
	{
		x=heap[1];
		sterge(1);
		ut[x]=1;
		
		for(it=a[x].begin();it!=a[x].end();it++)
		{
			if(ut[it->first])
				continue;
			if(cost[it->first]>it->second)
			{
				cost[it->first]=it->second;
				tata[it->first]=x;
				
				upHeap(poz[it->first]);
			}
		}
	}
	
	for(i=2;i<=n;i++)
		sol+=cost[i];
	
	printf("%d\n%d\n",sol,n-1);
	for(i=2;i<=n;i++)
		printf("%d %d\n",tata[i],i);
	
	return 0;
}