#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
struct muchie
{
  int t,x,c;
};
class compar
{
  public:
  bool operator()(muchie a,muchie b)
  {return a.c>b.c;}
};
priority_queue<muchie,vector<muchie>,compar> q;

vector<muchie> a[20001],sol;

muchie aux;
int s[20001],n;
int main()
{
  int m,i,mini=1,nr=0,ct=0,aux1;
  freopen("apm.in","rt",stdin);
  freopen("apm.out","wt",stdout);

  scanf("%ld%ld",&n,&m);
  for(i=1;i<=m;i++)
  {
    scanf("%ld%ld%ld",&aux.t,&aux.x,&aux.c);
   a[aux.t].push_back(aux);
   aux1=aux.t,aux.t=aux.x,aux.x=aux1;
  a[aux.t].push_back(aux);
  }
  s[1]=1;
  while(nr<n-1)
  {
  for(i=0;i<a[mini].size();i++)
  {
    if(s[a[mini][i].x]==0)
    q.push(a[mini][i]);
  }
  while(s[q.top().x]==1)
  q.pop();
  aux=q.top();
  sol.push_back(aux);
  ct+=aux.c;
  mini=aux.x;
  s[aux.x]=1;
  nr++;
  }
  printf("%ld\n%ld\n",ct,n-1);
  for(i=0;i<sol.size();i++)
  printf("%ld %ld\n",sol[i].t,sol[i].x);
  }