#include <cstdio>
#include <algorithm>
#include <time.h>
#include <stdlib.h>

using namespace std;

struct edge
{
    int nod1,nod2,d;
};

bool cmp (edge x,edge y)
{
    return x.d<y.d;
}

edge g[400001],sol[400001];
int v[200001];

int Find (int x)
{
    if (x==v[x])
    {
        return x;
    }
    else
    {
        v[x]=Find(v[x]);
        return v[x];
    }
}

void Union (int x,int y)
{
    int xx,yy;
    xx=Find(x);
    yy=Find(y);
    if (xx!=yy)
    {
        int r=rand()%2+1;
        if (r==1)
        {
            v[yy]=xx;
        }
        else
        {
            v[xx]=yy;
        }
    }
}

int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);

    int n,m,i;
    scanf ("%d %d",&n,&m);

    srand(time(NULL));

    int a,b,c;
    edge G;
    for (i=1; i<=m; i++)
    {
        scanf ("%d %d %d",&a,&b,&c);
        G.nod1=a;
        G.nod2=b;
        G.d=c;
        g[i]=G;
    }

    sort (g+1,g+m+1,cmp);

    for (i=1; i<=n; i++)
    {
        v[i]=i;
    }

    int cost=0,nr=0;

    for (i=1; i<=m; i++)
    {
        if (Find(g[i].nod1)!=Find(g[i].nod2))
        {
            Union(g[i].nod1,g[i].nod2);
            cost+=g[i].d;
            nr++;
            sol[nr]=g[i];
        }
    }

    printf ("%d\n%d\n",cost,nr);

    for (i=1; i<=nr; i++)
    {
        printf ("%d %d\n",sol[i].nod1,sol[i].nod2);
    }

    return 0;
}