#include<cstdio>
#include<algorithm>

using namespace std;
int n,m,x,y,z,cost;

struct muchie
{
    int x,y,c,is=0;
};

muchie v[400005];

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

int parents[200005];

int parent(int a,int b)
{
    int a1=a,b1=b;
    while(parents[a1]!=a1)
    {
        a1=parents[a1];
    }
    while(parents[b1]!=b1)
    {
        b1=parents[b1];
    }
    return a1==b1;
}

void join(int a,int b)
{
    int a1=a,b1=b,a2=1,b2=1;
    while(parents[a1]!=a1)
    {
        a1=parents[a1];
        a2++;
    }
    while(parents[b1]!=b1)
    {
        b1=parents[b1];
        b2++;
    }
    if(a2<b2)
        parents[a1]=b1;
    else parents[b1]=a1;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        parents[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        v[i].x=x;
        v[i].y=y;
        v[i].c=z;
    }
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(!parent(v[i].x,v[i].y))
        {
            join(v[i].x,v[i].y);
            cost+=v[i].c;
            v[i].is=1;
        }
    }
    printf("%d\n%d\n",cost,n-1);
    for(int i=1;i<=m;i++)
        if(v[i].is)
            printf("%d %d\n",v[i].x,v[i].y);
    return 0;
}