#include<cstdio>
#include<vector>
#include<algorithm>
#define infile "apm.in"
#define outfile "apm.out"
#define n_max 200005
#define m_max 400005
using namespace std;


void citeste();
void rezolva();
void afiseaza();


struct muchie 
{ 
	int n1,n2,cost;
} G[m_max];

int apm[n_max], T[n_max], R[n_max];
int n,m,cmin,nrm;



void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=m;i++)
		scanf("%d %d %d", &G[i].n1, &G[i].n2, &G[i].cost);
	
	fclose(stdin);
}

void init()
{
	for(int i=1;i<=n;i++)
		T[i]=i, R[i]=1;
}


int mycmp(muchie a, muchie b)
{
	return a.cost < b.cost;
}


int cauta(int x)
{
	int r,y;
	
	for(r=x; T[r] != r; r = T[r]);
	
	while(T[x]!=x)
	{
		y = T[x];
		T[x]=r;
		x=y;
	}
	
	return r;
}



void uneste(int x, int y)
{
	if(R[x] < R[y])
		T[x] = y;
	else
		T[y] = x;
	
	if(R[x] == R[y])
		R[x]++;
}




void rezolva()
{
	sort(G+1,G+m+1,mycmp);
	
	int m1,m2;
	
	for(int i=1;i<=m && nrm < n-1; i++)
	{
		m1 = cauta(G[i].n1);
		m2 = cauta(G[i].n2);
		
		if (m1 != m2) 
		{
			apm[++nrm]=i;
			cmin+=G[i].cost;
			
			uneste(m1, m2);
		}
	}
}



void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",cmin);
	
	printf("%d\n",nrm);
	
	for(int i=1;i<=nrm;i++)
		printf("%d %d\n",G[apm[i]].n1, G[apm[i]].n2);
	
	fclose(stdout);
}

int main()
{
	citeste();
	init();
	rezolva();
	afiseaza();
	
	return 0;
}