#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
const int maxn=400100;
int gr[maxn],x[maxn],y[maxn],indice[maxn],cost[maxn];
int n,m,i;
vector<int> Apm;



int padure(int i)
{
if(gr[i]==i)  return i;
gr[i]=padure(gr[i]);
return gr[i];
}

void reun(int i, int j)
{
gr[padure(i)]=padure(j);

}


inline bool cmp(int i, int j)
{

	return (cost[i]<cost[j]);
}
int main()
{
	
	ifstream f ("apm.in");
  ofstream g ("apm.out");
    int sol;
    sol=0;



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

  for(i=1;i<=n;i++)
  gr[i]=i;
  sort(indice+1, indice+1+m,cmp);
   for(i=1;i<=m;i++)
    if(padure(x[indice[i]])!=padure(y[indice[i]]))
    {
      sol+=cost[indice[i]];
      reun(x[indice[i]],y[indice[i]]);
      Apm.pb(indice[i]);

    }
    g<<sol<<"\n"<<n-1<<"\n";

    for(i=0;i<n-1;i++)
    g<<x[Apm[i]]<<" "<<y[Apm[i]]<<"\n";

      return 0;
}