#include<cstdio>
#include<algorithm>
using namespace std;
struct muchie
{
    int x,y,c;
};
muchie v[400005];
int t[200005],h[200005];
int n,m;
int sol[400005];
inline int cmp(muchie a,muchie b)
{
    return a.c<b.c;
}
int findset(int x)
{
    while(t[x]!=x)
        x=t[x];
    return x;
}
void unionset(int x,int y)
{
    if(h[x]==h[y])
    {
        h[x]++;
        t[y]=x;
    }
    else
        if(h[x]>h[y])
            t[y]=x;
        else
            t[x]=y;
}
int main()
{
    int i,cm,n,tx,ty,val;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=n;i++)
        t[i]=i;
    for(i=1;i<=m;i++)
        scanf("%d %d %d\n",&v[i].x,&v[i].y,&v[i].c);
    sort(v+1,v+m+1,cmp);
    cm=0;
    n=0;
    val=1;
    for(i=1;i<=m;i++)
    {
        tx=findset(v[i].x);
        ty=findset(v[i].y);
        if(tx!=ty)
        {
            unionset(tx,ty);
            cm=cm+v[i].c;
            n++;
            sol[val]=i;
            val++;
        }
    }
    printf("%d\n%d\n",cm,n);
    for(i=1;i<val;i++)
        printf("%d %d\n",v[sol[i]].y,v[sol[i]].x);
    return 0;
}