#include<stdio.h>
#include<algorithm>
#define Nmx 200005

using namespace std;

int n,m,nr,tata[Nmx];
struct muchi
{
    int x,y,c,t;
};
muchi A[Nmx*2];
struct cmp
{
    bool operator()(const muchi &a,const muchi &b) const
    {
        return a.c<b.c;
    }
};

void citire()
{
    scanf("%d%d",&n,&m);
    int X,Y,C;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&X,&Y,&C);
        A[++nr].x=X;
        A[nr].y=Y;
        A[nr].c=C;
    }
}

int rad(int x)
{
    int L=x;
    while(tata[L]!=L)
        L=tata[L];
    while(tata[x]!=x)
    {
        int y=tata[x];
        tata[x]=L;
        x=y;
    }
    return L;
}

void solve()
{
    sort(A+1,A+nr+1,cmp());
    for(int i=1;i<=n;++i)
        tata[i]=i;

    int sol=0,sum=0;
    for(int i=1;i<=nr&&sol<n-1;++i)
    {
        if(rad(A[i].x)!=rad(A[i].y))
        {
            tata[rad(A[i].x)]=tata[rad(A[i].y)];
            A[i].t=1;
            sum+=A[i].c;
            ++sol;
        }
    }
    printf("%d\n%d\n",sum,sol);
    for(int i=1;i<=nr;++i)
        if(A[i].t==1)
            printf("%d %d\n",A[i].x,A[i].y);
}

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