#include<algorithm>
#include<queue>
using namespace std;
#define N_MAX 200010

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

typedef pair <int,int> p;
vector <p> a[N_MAX];
vector <p> ::iterator it;

int cost[N_MAX],tata[N_MAX];
bool ut[N_MAX],inHeap[N_MAX];

int heap[N_MAX],poz[N_MAX],dimHeap;

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(cost[ heap[x>>1] ]>cost[ heap[x] ])
		upHeap(x);
	else
		downHeap(x);
}

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=1;i<=n;i++)
		cost[i]=(1<<30);
	cost[0]=-(1<<30)-(1<<29);
	
	ut[1]=1;
	inHeap[1]=1;
	
	int nd,ct;
	for(it=a[1].begin();it!=a[1].end();it++)
	{
		nd=it->first;
		ct=it->second;
		
		cost[nd]=ct;
		tata[nd]=1;
		
		inHeap[nd]=1;
		heap[++dimHeap]=nd;
		poz[nd]=dimHeap;
		
		upHeap(poz[nd]);
	}
	int ndd,ctt;
	while(dimHeap)
	{
		nd=heap[1];
		
		sterge(1);
		
		ut[nd]=1;
		for(it=a[nd].begin();it!=a[nd].end();it++)
		{
			ndd=it->first;
			ctt=it->second;
			if(ut[ndd])
				continue;
			if(cost[ndd]>ctt)
			{
				if(inHeap[ndd])
					sterge(poz[ndd]);
				
				cost[ndd]=ctt;
				tata[ndd]=nd;
					
				inHeap[ndd]=1;
				heap[++dimHeap]=ndd;
				poz[ndd]=dimHeap;
				upHeap(poz[ndd]);
			}
		}
	}
	
	int sol=0;
	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;
}