#include<cstdio>
#include<vector>
#define nmax 200001
using namespace std;

struct nod
{
   int next,c;
} AUX;

struct heap
{
   int n1,n2,c;
} AUX2;

vector < vector < nod > > a(nmax);
vector < vector < nod > > :: iterator itg ;
vector < nod >  :: iterator it ;
vector < heap > HEAP(400001);
vector < heap > scris(nmax);
vector < bool > viz(nmax);

int n,m,k,nr,S;

void read();
void pushup(int n);
void solve();
void combine(int k,int n);
void write();

int main()
{
   freopen ("apm.in","r",stdin);
   freopen ("apm.out","w",stdout);
   read();
   solve();
   write();
   return 0;
}

void solve()
{
   int nt;
   while (nr&&k!=n)
   {
      nt=HEAP[1].n2;
      if (viz[nt])
      {
         swap(HEAP[1],HEAP[nr]);
         --nr;
         combine(1,nr);
      }
      else 
      {
         AUX2.n1=nt;
         ++k;
         scris[k]=HEAP[1];
         S+=HEAP[1].c;
         viz[nt]=1;
         swap(HEAP[1],HEAP[nr]);
         --nr;
         combine(1,nr);
         for (it=a[nt].begin();it!=a[nt].end();++it)
           if (!viz[(*it).next])
           {
            AUX2.n2=(*it).next;
            AUX2.c=(*it).c;
            ++nr;
            HEAP[nr]=AUX2;
            pushup(nr);
         }
     }
   }
}      

void read()
{
   int x,y,ct,i;
   int ct2;
   scanf("%d%d",&n,&m);
   for (i=1;i<=m;++i)
   {
      scanf("%d%d%d",&x,&y,&ct2);
      AUX.c=ct2;
      AUX.next=y;
      a[x].push_back(AUX);
      AUX.next=x;
      a[y].push_back(AUX);
   }
   
   viz[1]=1;
   
   AUX2.n1=1;
   for (it=a[1].begin();it!=a[1].end();++it)
   {
      AUX2.n2=(*it).next;
      AUX2.c=(*it).c;
      ++nr;
      HEAP[nr]=AUX2;
      pushup(nr);
   }
}

void pushup(int n)
{
   heap Z;
   Z=HEAP[n];
   int t,c;
   t=n>>1;
   c=n;
   while (t&&HEAP[t].c>Z.c)
   {
      HEAP[c]=HEAP[t];
      c=t;
      t=t>>1;
   }
   HEAP[c]=Z;
}

void combine(int k,int n)
{
   heap Z;
   int t,c;
   Z=HEAP[k];
   t=k;
   c=k<<1;
   if (HEAP[c+1].c<HEAP[c].c)
      ++c;
   while(Z.c>HEAP[c].c&&c<=n)
   {
      HEAP[t]=HEAP[c];
      t=c;
      c=c<<1;
      if (HEAP[c+1].c<HEAP[c].c)
         ++c;
   }
   HEAP[t]=Z;
}
   
void write()
{
   int i;
   printf("%d\n%d\n",S,k);
   for (i=1;i<=k;++i)
      printf("%d %d\n",scris[i].n1,scris[i].n2);
}