#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,m,viz[1000],x[1000],xb[1000]; float mini,cost[1000];
vector <pair <int,int> > v[1000];
int back(int k)
{
	int j,l,i;
	if(k==n)
	{
		for(j=0;j<v[x[k-1]].size();j++)
			if(v[x[k-1]][j].first==0)
			{
				cost[k]=cost[k-1]+v[x[k-1]][j].second;
				if(cost[k]<mini)
				 {	for(l=0;l<n;l++)
						xb[l]=x[l];
				 mini=cost[k];
				 }
					
				cost[k]=cost[k]-v[x[k-1]][j].second;
			    break;
			}
		
	}
	else
		for(i=0;i<v[x[k-1]].size();i++)
			if(viz[v[x[k-1]][i].first]==0)
			{
				viz[v[x[k-1]][i].first]=1;
				x[k]=v[x[k-1]][i].first;
				cost[k]=cost[k-1]+v[x[k-1]][i].second;
				back(k+1);
				viz[v[x[k-1]][i].first]=0;
				cost[k]=cost[k]-v[x[k-1]][i].second;
			}
			
}
int main()
{
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");
	f>>n>>m;
	int i,j,k,l;
	for(k=1;k<=m;k++)
	{
		f>>i;
		f>>j;
		f>>l;
		v[i].push_back(make_pair(j,l));
	//	v[j].push_back(i);
	}
	viz[0]=1;
	x[0]=0;
	mini=400000000000;
	back(1);
	for(i=0;i<n;i++)
		g<<xb[i]<<" ";
	g<<endl<<mini;
		
}