#include <fstream>
#include <vector>
#define nmax 200001
#define inf 1000000000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct varf{int x, c;};
int n,m;
vector <varf> G[nmax];
int cmin[nmax],start;
int prec[nmax];
bool sel[nmax];

void citire();
void prim();
void afisare();
int main()
{
    citire();
    prim();
    afisare();
    return 0;
}
void citire()
{  varf aux;
   int i,x,y,cost;
   fin>>n>>m;
   start=1;
   for (i=0; i<m; i++)
      {
         fin>>x>>y>>cost;
         //adaug pe x in lista adiacenta a lui y
         aux.x=y;
         aux.c=cost;
         G[x].push_back(aux);
         aux.x=x;
         G[y].push_back(aux);
      }
   sel[start]=1;
   for (i=1; i<=n; i++)
      cmin[i]=inf;
   //parcurg lista de adiacenta a lui start
   cmin[start]=0;
   for (i=0; i<G[start].size(); i++)
      {
         cmin[G[start][i].x]=G[start][i].c;
         prec[G[start][i].x]=start;
      }
}
void prim()
{int i,j,minim, vfmin;
   for (i=0; i<n-1; i++)
      {
         //determin varful minim
         minim=inf+1;
         for (j=1; j<=n; j++)
            if (!sel[j] && cmin[j]<minim)
               {
                  minim=cmin[j];
                  vfmin=j;
               }
         sel[vfmin]=1;
         //actualizez
         for (j=0; j<G[vfmin].size(); j++)
            if (!sel[G[vfmin][j].x] && cmin[G[vfmin][j].x]>G[vfmin][j].c)
               {
                  cmin[G[vfmin][j].x]=G[vfmin][j].c;
                  prec[G[vfmin][j].x]=vfmin;
               }
      }
}
void afisare()
{
   int ct=0,i;
   for (i=1; i<=n; i++)
      ct+=cmin[i];
   fout<<ct<<'\n'<<n-1<<'\n';
   for (i=1; i<=n; i++)
      if (i!=start)
         fout<<i<<' '<<prec[i]<<'\n';
}