#include <stdio.h>


struct graf  {long x, y, c;};

graf g[100];
long n, m, p[100], h[100], sol[100], suma, nrsol;

void makeSet(int u);
int findSet(int u);
void setUnion(int u, int v);
long part(long jos, long sus);
void quicksort(long jos, long sus);

int main()
{
	long i, j, temp;
	freopen("kruskal.in", "r", stdin);
	freopen("kruskal.out", "w", stdout);
	scanf("%ld%ld", &n, &m);
	for (i=0; i<m; i++)
	  scanf("%ld%ld%ld", &g[i].x, &g[i].y, &g[i].c);  
	for (i=1; i<=n; i++)
	  makeSet(i);	  
	quicksort(0, m-1);
	for (i=0; i<m; i++)
	{
        if (findSet(g[i].x)!=findSet(g[i].y))
        {
           sol[nrsol++]=i;
	       suma+=g[i].c;           
           setUnion(g[i].x, g[i].y);
           if (nrsol==(n-1))
             break;
        }
    }
	printf("%ld\n%ld\n", suma, nrsol);
	for (i=0; i<nrsol; i++)
		printf("%ld %ld\n", g[sol[i]].x, g[sol[i]].y);    
	return 0;
}

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 setUnion(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]++;
     }
}
	
long part(long jos, long sus)
{
	long p=jos, u=sus;
    graf t;
	while (p<u)
	{
		while ((g[p].c<=g[jos].c)&&(p<=u))
			p++;
		while ((g[u].c>g[jos].c)&&(p<=u))
			u--;
		if (p<u)
		{
    	t=g[p];
		  g[p]=g[u];
		  g[u]=t;
		}
	}
	t=g[jos];
	g[jos]=g[u];
	g[u]=t;
	return u;
}

void quicksort(long jos, long sus)
{
	long p;
	if (jos<sus)
	{
	  p=part(jos, sus);
		quicksort(jos, p-1);
		quicksort(p+1, sus);
	}
}