#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define Nmx 200005

using namespace std;

int n,m,nr,tata[Nmx];
struct da
{
    int x,y,c,t;
}A[Nmx*2];

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

vector< pair<int,int> > G[Nmx];

void citire()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=n;++i)
        tata[i]=i;
    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;
        A[nr].t=0;
    }
}

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

void solve()
{
    sort(A+1,A+nr+1,cmp());
    int nrs=0,sum=0;
    for(int i=1;i<=nr&&nrs<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;
            ++nrs;
        }
    printf("%d\n%d\n",sum,n-1);
    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;
}