#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxm 400002
#define maxn 200002
#define cc first
#define xx second.first
#define yy second.second
#define pb push_back
#define mkp make_pair

using namespace std;


int n,m,i,x,y,cst,nr,zcst,radx,rady;
int parinte[maxn];

vector <pair<int,pair<int,int> > > vmu;
vector <pair<int,int> > vans ;
vector <int> lst[maxn];

int frad(int nod)
{
    int rad=nod;
    while (parinte[rad]>0)
    {
        rad=parinte[rad];
    }//int rfin=rad;
    return rad;
}

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

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

    for (i=0; i<m; ++i)
    {
        scanf ("%d%d%d",&x,&y,&cst);
        lst[x].pb(y);
        lst[y].pb(x);
        vmu.pb(mkp(cst,mkp(x,y)));
    }
    //nr=n
    sort (vmu.begin(),vmu.end());
    nr=n;

    for (i=1;i<=m;++i)
    {
        parinte[i]=-1;
    }

    for (i=0; i<m; ++i)
    {
        cst=vmu[i].cc;
        x=vmu[i].xx;
        y=vmu[i].yy;

        radx=frad(x);
        rady=frad(y);


        if (radx!=rady)
        {
            --nr;
            vans.pb(mkp(y,x));
            zcst+=cst;

            if (parinte[radx]<parinte[rady])
            {
                parinte[radx]+=parinte[rady];
                parinte[rady]=radx;
            }
            else
            {
                parinte[rady]+=parinte[radx];
                parinte[radx]=rady;
            }

        }

        if (nr==1)
        {
            break;
        }
    }
    printf("%d\n",zcst);
    printf("%d\n",n-1);

    for (i=0;i<n-1;++i)
    {
        printf("%d %d\n",vans[i].first,vans[i].second);
    }

    return 0;
}