#include <fstream>
#define INF 999999
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int d[21],t[21],cost[21][21],i,j,x,y,c,n,m,s;
bool sel[21];

void Prim (int nod)
{
    for (i=1;i<=n;i++) d[i]=INF,sel[i]=false;
    d[nod]=0;t[nod]=0;
    for (i=1;i<=n;i++)
    {
        int min=INF;
          for (int j=1;j<=n;j++)
            if (d[j]<min && !sel[j]) min=d[j],nod=j;
         sel[nod]=true;
         for (j=1;j<=n;j++)
           if (cost[j][nod]<d[j] && cost[j][nod]!=0 && !sel[j]) d[j]=cost[j][nod],t[j]=nod;
    }
}
int main()
{
   f>>n>>m;
   for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
        cost[i][j]=INF;
   for (i=1;i<=n;i++) cost[i][i]=0;
   for (i=1;i<=m;i++)
       f>>x>>y>>c,cost[x][y]=cost[y][x]=c;
for (i=1;i<=n;i++)
Prim(1);
for (i=1;i<=n;i++) s+=d[i];
g<<s<<'\n';
g<<n-1<<'\n';
for (i=1;i<=n;i++) g<<i<<' '<<t[i]<<'\n';
return 0;
}