#include<iostream>
#include<fstream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
using namespace std;

struct muchii
{
	int a,b,c;
} m[400000];
struct muchii2
{
	long a1,b1;
} A[200000];
int p[200000],h[200000],C,k,mu,n;
int compare(const void *x,const void *y)
{
	return ((*(muchii*)x).c-(*(muchii*)y).c);
}
void makeset(int u)
{
	p[u]=0;
	h[u]=0;
}
int findset(int u)
{
	if (p[u]==0)
		return u;
	p[u]=findset(p[u]);
	return p[u];
}
void union1(int u, int v)
{
	u=findset(u);
	v=findset(v);
	if (h[u]>h[v])
		p[v]=u;
	else 
	{
		p[u]=v;
		if (h[u]==h[v])
			h[v]++;
	}
}
void sort()
{
	int i,j;
	muchii aux;
	for (i=0;i<mu-1;i++)
		for (j=i+1;j<mu;j++)
			if (m[i].c>m[j].c) 
			{
				aux=m[i];
				m[i]=m[j];
				m[j]=aux;
			}
}
void quicksort(muchii m[], long left, long right)
{
	int i = left, j = right;
    muchii tmp;
    int pivot;
	srand(time(NULL));
	int p;
	p=rand()%(j-i)+i;
	pivot=m[p].c;
    /* partition */
    while (i <= j) 
	{
		while (m[i].c < pivot)
            i++;
		while (m[j].c > pivot)
            j--;
		if (i <= j) 
		{
			tmp = m[i];
            m[i] = m[j];
            m[j] = tmp;
            i++;
            j--;
        }
    };
    /* recursion */
    if (left < j)
		quicksort(m, left, j);
	if (i < right)
        quicksort(m, i, right);
}
void kruskal()
{
	int i;
	k=0;
	C=0;
	/*for(i=0;i<n;i++)
		makeset(i);*/
	//quicksort(m,0,mu-1);
	qsort(m,mu,sizeof(muchii),compare);
	for (i=0; i<mu;i++)
	{
		if (findset(m[i].a)!=findset(m[i].b))
		{
			A[k].a1=m[i].a;
			A[k].b1=m[i].b;
			k++;
			C=C+m[i].c;
			union1(m[i].a,m[i].b);
			if (k==mu-1)
				break;
		}
	}
}
int main()
{
	freopen ("apm.in","r",stdin);
	freopen ("apm.out","w",stdout);
	int i;
	scanf("%i%i",&n,&mu);
	for (i=0;i<mu;i++)
		scanf("%i%i%i",&m[i].a,&m[i].b,&m[i].c);
	kruskal();
	printf("%i\n%i\n",C,n-1);
	for (i=0;i<k;i++)
		printf("%i%i\n",A[i].a1,A[i].b1);
	return 0;
}