#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
#define fr for

using namespace std;


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

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

int frad(int nod)
{
    int rad=nod;
    while (parinte[rad])
    {
        rad=parinte[rad];
    }
    int rfin=rad;

   /* rad=nod;
    while (parinte[rad])
    {
        int aux=rad;
        rad=parinte[rad];
        parinte[aux]=rfin;
    }
    */

    return rfin;
}



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=0; i<m; ++i)
    {
        cst=vmu[i].cc;
        x=vmu[i].xx;
        y=vmu[i].yy;

        memset(ver,0,sizeof(ver));

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


        if (radx!=rady)
        {
            --nr;


            if (parinte[y])
                parinte[x]=y;
            else parinte[y]=x;

            zcst+=cst;
            vans.pb(mkp(y,x));
        }
        else
        {
            int kk=1;
        }
        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;
}