#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;
int i,x,y,n,c,m,k,nr,cost,r[1000],t[1000];

struct muchie{
int n1;
int n2;
int cost;}l[1000];
muchie a[1000];
void lipesc(int x,int y)
{	if(r[x]>r[y])
		t[y]=x;
	else
		t[x]=y;
	if(r[x]==r[y])
		r[y]++;
}

int gasesc(int x)
{	int p=x,m,l=x;
	while(t[l]!=l)
		l=t[l];
	while(t[p]!=p)
	{	m=t[p];
		t[p]=l;
		p=m;
	}
	return l;
}

int cmp(muchie q,muchie w)
{
    return q.cost<w.cost;
}
int main()
{   freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
       {scanf("%d%d%d",&x,&y,&c);
        l[++k].n1=x;
        l[k].n2=y;
        l[k].cost=c;
       }
    sort(l+1,l+m+1,cmp);
   for(i=1;i<=n;i++)
        {
            t[i]=i;
            r[i]=1;
        }
   for(i=1;nr<n;i++)
    {  if(gasesc(l[i].n1)!=gasesc(l[i].n2))
          {   cost+=l[i].cost;
              nr++;
            lipesc(l[i].n1,l[i].n2);
            a[nr].n1=l[i].n1;
            a[nr].n2=l[i].n2;
            a[nr].cost=l[i].cost;
            }

    }
    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(i=1;i<n;i++)
    printf("%d %d %d\n",a[i].n1,a[i].n2,a[i].cost)
;        return 0;
}