#include <stdio.h>

#define DIM 400000
#define max 200000
struct muchie {int x; int y; int cost;} a[DIM], cost[max]; 
int tata[max], rang[max];
int n, m, nr, c;
void qsort(int st, int dr)
{
	muchie tmp;
    int i=st;
	int j=dr;
	int mij=a[(st+dr)/2].cost;
	do
	{
	   while (a[i].cost<mij) ++i;
	   while (a[j].cost>mij) --j;
	   if (i<=j)
	   {
            tmp=a[i];
            a[i]=a[j];
            a[j]=tmp;
	       	++i; --j;
    		}
	}while (i<=j);
	if (i<dr) qsort(i,dr);
	if (st<j) qsort(st,j);
    }   

int find(int k)
{
    int tmp, r;
    for (r=k; r!=tata[r]; r=tata[r]);
    while (k!=tata[k])
    {
        tmp=tata[k];
        tata[k]=r;
        k=tmp;
        }
    return r;
    }
    
void unite(int k, int l)
{
    if (rang[k]>rang[l])
        tata[l]=k;
    else 
        tata[k]=l;
    if (rang[k]==rang[l])
        rang[l]++; 
    }

void apm()
{
    int i;
    for (i=1; nr<n-1; ++i) 
        if (find(a[i].x)!= find(a[i].y)) 
        { 
            c=c+a[i].cost; 
            cost[++nr]=a[i]; 
            unite (find (a[i].x),find (a[i].y)); 
        } 
    }

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; ++i)
	  scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].cost);
	for (int i=1; i<=n; ++i)
	{
        tata[i]=i;
        rang[i]=1;    
        }
	qsort(1,m);
	apm();
	printf ("%d\n%d\n",c,nr); 
    for (int i=1; i<=nr; ++i) 
        printf ("%d %d\n",cost[i].x,cost[i].y); 
    return 0;
}