#include <fstream>
#define INF 3333

using namespace std;
ifstream fin("prim.in");
ofstream fout("prim.out");

struct muchie
{
	int y, c;
} a[105][105];

int n, m, vfmin[105], cmin[105], d[105], start = 1;
bool s[105];

void read();
void Prim(int);
void write();

int main()
{
	read();
	Prim(start);
	write();

	return 0;
}

void read()
{
	int i, x, y, c;

	fin >> n >> m;

	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		a[x][++d[x]].y = y;
		a[x][d[x]].c = c;
		a[y][++d[y]].y = x;
		a[y][d[y]].c = c;
	}

	s[start] = 1;

	for (i = 1; i <= n; i++)
	{
		vfmin[i] = start;
		cmin[i] = INF;
	}

	vfmin[start] = cmin[start] = 0;

	for (i = 1; i <= d[start]; i++)
		cmin[a[start][i].y] = a[start][i].c;
}

void Prim(int start)
{
	int i, j, vf, minn;

	for (i = 1; i <= n; i++)
	{
		// determin un varf neselectat de cost minim
		minn = INF;
		for (j = 1; j <= n; j++)
			if (!s[j] && cmin[j] < minn)
			{
				minn = cmin[j];
				vf = j;
			}
		s[vf] = 1;
		// actualizez eventual costurile catre celelalte varfuri neselectate
		for (j = 1; j <= d[vf]; j++)
		{
			if (!s[a[vf][j].y] && cmin[a[vf][j].y] > a[vf][j].c)
			{
				cmin[a[vf][j].y] = a[vf][j].c;
				vfmin[a[vf][j].y] = vf;
			}
		}
	}
}

void write()
{
	int i, sum = 0;

	for (i = 1; i <= n; i++)
		sum += cmin[i];
	fout << sum << '\n';

	for (i = 1; i <= n; i++)
		fout << vfmin[i] << ' ';
	fout << '\n';
}