#include <fstream>
#include <algorithm>
using namespace std;
int Cost,c[200002],x[200002],y[200002],Answer[200002],A,n,m,Ind[200002],multime[200002];
bool cmp(int i,int j)
{
  return(c[i]<c[j]);
}
int grupa(int i)
{
  if(multime[i]==i) return i;
  multime[i]=grupa(multime[i]);
  return multime[i];
}
void reunite(int i,int j)
{
  multime[grupa(i)]=grupa(j);
}
int main()
{
  int i;
    ifstream fi("apm.in");
    ofstream fo("apm.out");
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
      fi>>x[i]>>y[i]>>c[i];
      Ind[y[i]]=x[i];
    }
    for(i=1;i<=n;i++) multime[i]=i;
    for(i=1;i<=n;i++) multime[i]=i;
    sort(Ind+1,Ind+m+1,cmp);
    for(i=1;i<=m;i++)
    {
      if(grupa[x[Ind[i]]]!=grupa[y[Ind[i]]])
      {
        Cost+=c[Ind[i]];
        reunite(x[Ind[i]],y[Ind[i]]);
        Answer[++A]=Ind[i];
      }
    }
    fo<<Cost<<"\n"<<n-1<<"\n";
    for(i=1;i<=n-1;i++) fo<<x[Answer[i]]<<" "<<y[Answer[i]]<<"\n";
    return 0;
}