#include <fstream>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
#define inf 30000
bool sel[20000],ok;
int d[20000],t[20000],n,m,i,j,Min,m1,m2,c,k,capm=0,a[20000][20000];
int main()
{
    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]=inf; a[j][i]=inf;
        }
    }
    for (i=1;i<=m;i++)
    {
        f>>m1>>m2>>c;
        a[m1][m2]=c,a[m2][m1]=c;
    }
    for (i=1;i<=n;i++)
    {
        d[i]=inf; t[i]=0; sel[i]=false;
    }
    d[1]=0;  // aleg sa incep de la nodul 1
    ok=true;
    while (ok)
    {
        Min=inf;
        for (i=1;i<=n;i++) if (d[i]<Min && !sel[i])
        {
            Min=d[i]; k=i;
        }
        if (Min==inf) ok=false;
        else
        {
            sel[k]=true;
            capm+=d[k];
            for (i=1;i<=n;i++) if (!sel[i] && d[i]>a[k][i] && a[k][i]!=0)
            {
                d[i]=a[k][i];
                t[i]=k;
            }
        }
    }
    g<<capm<<'\n';
    for (i=1;i<=n;i++) g<<t[i]<<" ";
    return 0;
}