#include <fstream>
#include <algorithm>
#define nmax 400005
#define vmax 100005

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct arbore
{
    int nod1, nod2, muchiecost;
};

struct raspuns
{
    int nodfinal1, nodfinal2;
};

raspuns ans[vmax];

int cmp(arbore a, arbore b)
{
    return a.muchiecost < b.muchiecost;
}

int rad[vmax], nrfii[vmax];

int calc_rad(int a)
{
  if(rad[a]==0)
     return a;
  else
     calc_rad(rad[a]);
}

arbore v[nmax];

int n, m, a, b, c, costminim, rada, radb, poz;

int main()
{
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>a>>b>>c;
        v[i].nod1 = a;
        v[i].nod2 = b;
        v[i].muchiecost = c;
    }
    sort(v+1, v+m+1, cmp);
    /*for(int i=1; i<=m; i++)
    {
        out<<v[i].nod1<<" "<<v[i].nod2<<" "<<v[i].muchiecost<<"\n";
    }*/
    for(int i=1; i<=m; i++)
    {
        rada = calc_rad(v[i].nod1);
        radb = calc_rad(v[i].nod2);
        if(rada!=radb)
        {
            costminim += v[i].muchiecost;
            ans[poz].nodfinal1 = v[i].nod2;
            ans[poz].nodfinal2 = v[i].nod1;
            poz++;
            if(nrfii[rada]>nrfii[radb])
            {
                nrfii[rada]+=nrfii[radb];
                rad[radb] = rada;
            }
            else
            {
                nrfii[radb]+=nrfii[rada];
                rad[rada] = radb;
            }
        }
    }
    out<<costminim<<"\n"<<n-1<<"\n";
    for(int i=0; i<n-1; i++)
    {
        out<<ans[i].nodfinal1<<" "<<ans[i].nodfinal2<<"\n";
    }
    return 0;
}