#include <stdio.h>
#include <algorithm>

using namespace std;

const int size = 400010;

struct muc
{
    int y,x,cost;
}a[size];

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

int rez[size];
int nr;
int n,m,Tati[size];

int T(int nod)
{
    if (Tati[nod]==nod)
        return nod;
    return Tati[nod]=T(Tati[nod]);
}

void citire()
{
    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
        scanf ("%d %d %d",&a[i].x,&a[i].y,&a[i].cost);
    sort(a,a+m,cmp());
    for (int i=1;i<=n;i++)
        Tati[i]=i;
}

void solve()
{
    int cost=0;
    for (int i=0;i<m;i++)
    {
        if (T(a[i].x)!=T(a[i].y))
        {
            Tati[T(a[i].x)]=Tati[a[i].y];
            rez[nr++]=i;
            cost+=a[i].cost;
        }
    }
    printf ("%d\n%d\n",cost,nr);
    for (int i=0;i<nr;i++)
        printf("%d %d\n",a[rez[i]].x,a[rez[i]].y);
}


int main ()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    citire();
    solve();
    return 0;
}