#include <fstream>
#include <set>
#include <iostream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define inf 200000000
int n,m;
struct nod
{ int info;
  int cost;
  int marcat;
  nod *urm;

} *g[1000];
void Addelem(nod *&prim,int y,int yy)
{ nod *q=new nod;
  q->info=y;
  q->marcat=0;
  q->cost=yy;
  q->urm=prim;
  prim=q;
}
int d[1000],t[1000],viz[1000];
int main()
{  fin>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++)
    { fin>>x>>y>>c;
      Addelem(g[x],y,c);
      Addelem(g[y],x,c);
    }


    for(int i=1;i<=n;i++)
      d[i]=inf;
    d[1]=0;
  set<pair<int,int> > Q;
    Q.insert(make_pair(d[1],1));

  for(int i=1;i<=n-1;i++)
    {
      x=Q.begin()->first;
      y=Q.begin()->second;
      Q.erase(Q.begin());
      viz[y]=1;
   for(nod *p=g[y];p!=NULL;p=p->urm)
       if(viz[p->info]==0)
        if(p->cost<d[p->info])

            { Q.erase(make_pair(d[p->info],p->info));
              d[p->info]=p->cost;
              Q.insert(make_pair(d[p->info],p->info));
              t[p->info]=y;
            }
    }
    int costtotal=0;
    for(int i=2;i<=n;i++)
        costtotal+=d[i];
        cout<<costtotal<<"\n";
        cout<<n-1<<"\n";
  for(int i=2;i<=n;i++)
    cout<<i<<" "<<t[i]<<"\n";//<<//d[i]<<"\n";


    return 0;
}