#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,q[200002],s=0,nr=0;

struct stru
{
    int d,a,b,u=0;
} v[400002];

bool rule(stru x, stru y)
{
    return (bool)(x.d<y.d);
}

int root(int x)
{
    int y=x,z;
    while(q[x]!=x)
        x=q[x];
    while(q[y]!=y)
    {
        z=q[y];
        q[y]=x;
        y=z;
    }
    return x;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i,j,ra,rb;
    scanf("%d %d",&n,&m);
    for(i=0;i<m;i++)
        scanf("%d %d %d",&v[i].a,&v[i].b,&v[i].d);
    sort(v,v+m,rule);
    for(i=1;i<=n;i++)
        q[i]=i;
    for(i=0;i<m;i++)
    {
        ra=root(q[v[i].a]);
        rb=root(q[v[i].b]);
        if(ra!=rb)
        {
            q[ra]=rb;
            v[i].u=1;
            s+=v[i].d;
            nr++;
        }
    }
    printf("%d\n%d\n",s,nr);
    for(i=0;i<m;i++)
        if(v[i].u==1)
            printf("%d %d\n",v[i].a,v[i].b);

    return 0;
}