#include<cstdio>
#include<algorithm>
using namespace std;
struct eu{int a,b,val;};
eu v[400001];
struct eu2{int x,y;};
eu2 vv[200001];
int rad[200001];
int i,n,m,s,cate;
int radacina(int nod)
    {
    if(rad[nod]==nod)
        return nod;
    else
        {
        rad[nod]=radacina(rad[nod]);
        return rad[nod];
        }
    }
bool sorting(eu a,eu b)
    {
    return a.val<b.val;
    }
int main ()
{
freopen("apm.out","w",stdout);
freopen("apm.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
    scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].val);
for(i=1;i<=n;i++)
    rad[i]=i;
sort(v+1,v+m+1,sorting);
for(i=1;i<=m;i++)
    {
    if(rad[radacina(v[i].a)]!=radacina(v[i].b))
        {
        rad[radacina(v[i].a)]=radacina(v[i].b);
        cate++;
        vv[cate].x=v[i].a;
        vv[cate].y=v[i].b;
        s+=v[i].val;
        }
    }
printf("%d\n",s);
printf("%d\n",cate);
for(i=1;i<=cate;i++)
    printf("%d %d\n",vv[i].x,vv[i].y);
return 0;
}