#include <algorithm>
using namespace std;

#define DIM 200005

struct muchie {int x,y,c;} v[DIM<<1],sol[DIM];
int t[DIM],r[DIM];
int n,m,nrm,cost;

void read ()
{
    int i;

    scanf ("%d%d",&n,&m);
    for (i=1; i<=m; ++i)
        scanf ("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
}

struct cmp
{
    bool operator () (const muchie &a,const muchie &b)
    {
        return a.c<b.c;
    }
};

void init ()
{
    int i;

    for (i=1; i<=n; ++i)
        t[i]=i;
    sort (v+1,v+m+1,cmp ());
}

int find (int x)
{
    if (x!=t[x])
        t[x]=find (t[x]);
    return t[x];
}

inline void unite (int x,int y)
{
    if (r[x]<r[y])
        t[x]=y;
    else
        t[y]=x;
    if (r[x]==r[y])
        ++r[x];
}

void solve ()
{
    int i;

    for (i=1; nrm<n-1 && i<=m; ++i)
        if (find (v[i].x)!=find (v[i].y))
        {
            cost+=v[i].c;
            sol[++nrm]=v[i];
            unite (find (v[i].x),find (v[i].y));
        }
}

void print ()
{
    int i;

    printf ("%d\n%d\n",cost,nrm);
    for (i=1; i<=nrm; ++i)
        printf ("%d %d\n",sol[i].x,sol[i].y);
}

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

    read ();
    init ();
    solve ();
    print ();

    return 0;
}