#include<iostream>
#include<vector>
#include<utility>
#include<string.h>
using namespace std;

#define mp make_pair
#define MAX_N 200001
#define INF 9999999

int n,m,cost,C[10000][10000],D[MAX_N],T[MAX_N];    
vector < pair<int,int> > muchii;

void init(void)
{
	int i,j;
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			if(i==j)
				C[i][j]=0;
			else
				C[i][j]=INF;
}
			

void read(void)
{
	int i,x,y,c;
	freopen("apm.in","r",stdin);
	scanf("%d %d",&n,&m);
	init(); //initializarea matricei costurilor
	for(i=1; i<=m; i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		C[x][y]=c;   C[y][x]=c; //graful este neorientat
	}
	fclose(stdin);
}


void apm_prim(int x)
{
	int i,min,nod,U[MAX_N],T[MAX_N];
	
	memset(U,0,sizeof(U)); 
	memset(T,0,sizeof(T)); 
	
	for(i=1; i<=n; i++)
	{
		D[i]=C[x][i];  
		T[i]=x;  
	}
	U[x]=1;
	
	while(1)
	{
		min=INF;  nod=-1;
		for(i=1; i<=n; i++)
			if(!U[i] && min>D[i])
			{
				min=D[i];
				nod=i;
			}
		if(min==INF)
			break;
		
		U[nod]=1; 
		cost+=D[nod];
		muchii.push_back(mp(T[nod],nod)); 
		
		for(i=1; i<=n; i++)
			if(D[i]>C[nod][i])
			{
				D[i]=C[nod][i];
				T[i]=nod;
			}
	}
	
}

void write(void)
{
	vector< pair<int,int> > ::iterator i;
	freopen("apm.out","w",stdout);
	
	printf("%d\n%d\n",cost,muchii.size());
	for(i=muchii.begin(); i!=muchii.end(); i++)
		printf("%d %d\n",i->first,i->second);
	fclose(stdout);
}


int main() 
{
	read();
	apm_prim(1);
	write();
	return 0;
}