#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

ifstream fin("date.in");

int viz[200001],cm[200001];

vector <int> m[200001],cost[200001],m1[200001];

int main()
{
    int n,x,y,c,i,k,min,sum=0,j,vecin;

    fin>>n>>k;
    for(i=1;i<=k;i++)
    {
     fin>>x>>y>>c;
     m[x].push_back(y);
     cost[x].push_back(c);
     m[y].push_back(x);
     cost[y].push_back(c);
    }

    for(i=1;i<=n;i++)
        cm[i]=10000;
    cm[1]=0;

    for(k=1;k<n;k++)
    {
     min=10000;
     for(i=1;i<=n;i++)
       if(viz[i]==0 && cm[i]<min)
         {min=cm[i];
          x=i;}

     min=10000;
     viz[x]=1;
     for(i=1;i<=m[x].size();i++)
         {
          vecin=m[x][i-1];
          c=cost[x][i-1];
          if(viz[vecin]==0 && c<=cm[vecin])
              {
               cm[vecin]=c;
               if(c<min)
               {
                min=c;
                y=vecin;
               }

              }
         }
     m1[x].push_back(y);
     m1[y].push_back(x);
    }

    for(i=1;i<=n;i++)
        sum+=cm[i];
    cout<<sum<<endl;

    for(i=1;i<=n;i++)
    {
        for(j=0;j<m1[i].size();j++)
            cout<<m1[i][j]<<" ";
    cout<<endl;
    }
    return 0;
}