//kruskal cu multimi disjuncte

#include <cstdio>
#include <algorithm>

using namespace std;

int n,m,used[200002],nrsol,cost,cnt;
int poz[200002],r[200002];
struct muchie { int x,y,cost,da;} z[400002];

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

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)
        {
            cost+=z[i].cost;
            nrsol++;
            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].cost);
    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;
}