#include<cstdio>
#include<algorithm>
using namespace std;
struct apm{int i,j,c;};
apm v[400001];
int sef[200001];
int h[200001];
struct afis{int a,b;};
afis r[200001];
bool sor(apm a,apm b)
{
    if(a.c<b.c)
        return true;
    return false;
}
int fnd(int i)
{
    if(sef[i]==i)
        return i;
    sef[i]=fnd(sef[i]);
    return sef[i];
}
void unin(int i,int j)
{
    int a=fnd(i);
    int b=fnd(j);
    if(h[a]==h[b])
    {
        h[a]++;
        sef[b]=a;
    }
    else
    {
        if(h[a]>h[b])
        {
            sef[b]=a;
        }
        else
        {
            sef[a]=b;
        }
    }
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,j=0,s=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v[i].i,&v[i].j,&v[i].c);
    }
    for(i=1;i<=n;i++)
    {
        sef[i]=i;
    }
    sort(v+1,v+m+1,sor);
    for(i=1;i<=m&&j<=n-2;i++)
    {
        if(fnd(v[i].i)!=fnd(v[i].j))
        {
            s+=v[i].c;
            unin(v[i].i,v[i].j);
            j++;
            r[j].a=v[i].i;
            r[j].b=v[i].j;
        }
    }
    printf("%d\n%d\n",s,j);
    for(i=1;i<=j;i++)
    {
        printf("%d %d\n",r[i].a,r[i].b);
    }
    return 0;
}