#include<iostream>
#include<fstream>
#define MAX_N 1000
#define INF 30000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,r,C[MAX_N][MAX_N],D[MAX_N],T[MAX_N],cost=0,U[MAX_N],A[2][MAX_N];
void prim2(int x)
{
    int i,min,nod;

    for(i=1;i<=n;i++)
        D[i]=C[x][i],T[i]=x;
    U[x]=1;
    while(1)
    {
        //printf("%d",x);
        min=INF;
        nod=-1;
        for(i=1;i<=n;i++)
            if(!U[i]&&min>D[i])
                min=D[i],nod=i;
                if(min==INF) break;

       U[nod]=1;
       cost+=D[nod];
       A[1][++A[0][0]]=nod;
       A[2][A[0][0]]=T[nod];
     //  printf("%d %d\n",T[nod],nod);
       for(i=1;i<=n;i++)
        if(D[i]>C[nod][i])
       {
           D[i]=C[nod][i];
           T[i]=nod;
       }
    }
    g<<cost<<"\n";
    g<<n-1<<"\n";

    for(i=1;i<A[0][0];i++)
        g<<A[1][i]<<" "<<A[2][i]<<"\n";
    g<<n<<" "<<T[n];
}
void citire()
{
    int i,j,x,y,c;
    f>>n;
    f>>m;
    for(i=1;i<=m;i++)
      {
          f>>x>>y>>c;
          C[x][y]=C[y][x]=c;
      }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(C[i][j]==0) C[i][j]=INF;
f.close();
}
int main()
{ int i;

citire();
for(i=1;i<=n;i++)
    C[i][i]=INF;
prim2(1);
}