#include <cstdio>
#include <algorithm>

using namespace std;

struct muchie { int x,y,c,da;} z[400002];

int n,m,nrsol,cost;
int poz[200002],r[200002];

bool operator<(muchie x, muchie y)
{
    return x.c<y.c;
}

int mult(int x)
{
    if(poz[x]==x)
        return poz[x];
    poz[x]=mult(poz[x]);
    return poz[x];
}

void reun(int x, int y)
{
    x=mult(x);
    y=mult(y);
    if(r[x]>r[y])
        poz[y]=x;
    else
    {
        poz[x]=y;
        if(r[x]==r[y])
            r[y]++;
    }
}

void kruskal()
{
    int m1,m2;
    for(int i=1;i<=m;i++)
    {
        m1=mult(z[i].x);
        m2=mult(z[i].y);
        if(m1!=m2)
        {
            nrsol++;
            cost+=z[i].c;
            z[i].da=1;
            reun(m1,m2);
        }
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        poz[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&z[i].x,&z[i].y,&z[i].c);
    sort(z+1,z+m+1);
    kruskal();
    printf("%d\n%d\n",cost,nrsol);
    for(int i=1;i<=m;i++)
        if(z[i].da==1)
            printf("%d %d\n",z[i].x,z[i].y);
    fclose(stdout);
    return 0;
}