#include<iostream>
#include<algorithm>
#include<fstream>
#include<vector>
#define pb push_back
const int maxi=4001000;
using namespace std;



int tatal[maxi],x[maxi],y[maxi],cost[maxi],indexare[maxi];
int n,m,cost_arbore;
vector <int> vector_nou;

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()
{
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.pb(indexare[i]);

        }
    }
  g<<cost_arbore;
  g<<endl;
g<<n-1;
    g<<endl;
    for(int i = 0;i < n-1 ; ++i)
        g<<x[vector_nou[i]]<<" "<<y[vector_nou[i]]<<endl;
    return 0;
}