#include<fstream>
using namespace std;
long nmax=99999;
int n,m,v,s[10002],t[10002];
long int a[10002][10002],min1;
ifstream f("apm.in");
ofstream g("apm.out");

void citire()
{int i,j,x,y,z;

 f>>n>>m;
 
 for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
     {if(i==j)
            a[i][j]=0;
      else
			a[i][j]=nmax;
      }
 
for(i=1;i<=m;i++)
 {f>>x>>y>>z;
  a[x][y]=a[y][x]=z;}
 
}
 
 
int cauta(int &zz)
{ min1=nmax;
  for(int i=1;i<=n;i++)
   if(s[i]!=0)
     if(a[i][s[i]]<min1)
            {min1=a[i][s[i]];
             zz=i;}
return min1;
}
 
void actualizeaza(int nod)
{for(int i=1;i<=n;i++)
   if(s[i])
      if(a[i][s[i]]>a[i][nod])
               s[i]=nod;
 
}
 
int main()
{ int k,i,j,cost=0;
citire();
s[1]=0;
for(i=2;i<=n;i++)
     s[i]=1;
 
int nod;
for(k=1;k<=n-1;k++)
   {min1=cauta(nod);
   t[nod]=s[nod];
   cost=cost+min1;
   s[nod]=0;
   actualizeaza(nod);
   }
 
g<<"costul este "<<cost<<'\n';
g<<"arborele de cost minimal ";
for(i=1;i<=n;i++)
  g<<t[i]<<" ";
 g.close();
 return 0;
}