#include<fstream>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
const int Nmax=1005,inf=2000000000;
int n,m,a[Nmax][Nmax],viz[Nmax],dad[Nmax],cost_max;
void read()
{int x,y,z;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
    {
        a[i][j]=inf;
        a[j][i]=inf;
    }

    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>z;
        a[x][y]=z;
        a[y][x]=z;
    }
}

void print()
{
    fout<<cost_max<<"\n";
    for(int i=1;i<=n;i++)
        fout<<dad[i]<<" ";
    fout<<"\n";
}

void prim(int p)
{int Min,nod;
    viz[p]=1;
    dad[p]=0;

    for(int i=1;i<=n;i++)
        if(i!=p)
          dad[i]=p;

    for(int k=0;k<n-1;k++)
    {
        Min=inf;
        nod=0;

        for(int i=1;i<=n;i++)
        {
            if(!viz[i] && a[i][dad[i]]<Min)
            {
                Min=a[i][dad[i]];
                nod=i;
            }
        }

        viz[nod]=1;
        cost_max+=Min;

        for(int i=1;i<=n;i++)
            if(!viz[i] && a[i][dad[i]]>a[i][nod])
                dad[i]=nod;
    }
}
int main()
{
read();
prim(1);
print();






fin.close();
fout.close();
return 0;
}