#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int t[200001],h[200001];
struct muchie
{
    int u;
    int v;
    int c;
};
muchie v[400001],f[200001];




int find(int x)
{
    int r,y;
    for(r=x;t[r]!=r;r=t[r]);
    while(t[x]!=r)
    {
        y=t[x];
        t[x]=r;
        x=y;
    }
    return r;
}




void Union(int x, int y)
{
    if(h[x]>h[y])
        t[y]=x;
    else
        if(h[x]==h[y])
        {
            ++h[x];
            t[y]=x;
        }
        else
            t[x]=y;
}





bool cmp(muchie a, muchie b)
{
    return a.c<b.c;
}





int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,i,j,m,tx,ty;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&v[i].u,&v[i].v,&v[i].c);
    for(i=1;i<=n;++i)
        t[i]=i;
    sort(v+1,v+m+1,cmp);
    j=0;
    for(i=1;i<=m;++i)
    {
        tx=find(v[i].u);
        ty=find(v[i].v);
        if(tx!=ty)
        {
            f[++j].u=v[i].u;
            f[j].v=v[i].v;
            f[j].c=f[j-1].c+v[i].c;
            Union(tx,ty);
        }
    }
    printf("%d\n%d\n",f[j].c,j);
    for(i=1;i<=j;++i)
        printf("%d %d\n",f[i].u,f[i].v);
    return 0;
}