#include<iostream>
#include<algorithm>
#include<fstream>


using namespace std;



int tatal[400001],x[400001],y[400001],cost[400001],indexare[400001],vector_nou[400001];
long n,m,cost_arbore;


int radacina(int i)
{
    if (tatal[i] == i) return i;
    tatal[i] = radacina(tatal[i]);
    return tatal[i];
}

void reuneste(int i,int k)
{
    tatal[radacina(i)] = radacina(k);
}

bool compara(int i,int k)
{
    return(cost[i] < cost[k]);
}

int main()
{int j=1;
ifstream f("apm.in");
           ofstream g("apm.out");
   f>>n>>m;

    for(int i = 1;i <= m;++i)
    {
    f>>x[i]>>y[i]>>cost[i];
      indexare[i] = i;
    }

    for(int i = 1;i <= n; ++i) tatal[i]=i;

    sort(indexare+1 ,indexare + m + 1,compara);
    for(int i = 1;i <= m; ++i)
    {
        if (radacina(x[indexare[i]]) != radacina(y[indexare[i]])){
cost_arbore=cost_arbore+ cost[indexare[i]];
            reuneste(x[indexare[i]],y[indexare[i]]);
           vector_nou[j]=indexare[i];
           j++;
        }
    }
  g<<cost_arbore;
  g<<"\n";
g<<n-1;
    g<<"\n";
    for(int i = 1;i < n ; ++i)
        g<<x[vector_nou[i]]<<" "<<y[vector_nou[i]]<<"\n";
    return 0;
}