#include <fstream.h>
#include <stdlib.h>
#include <time.h>


int n,e;
int**  value;
int* temporder;



int calculate()
{
	int leng=0;
	for (int i=1;i<n+1;i++)
		leng+=value[temporder[i]][temporder[i+1]];
	return leng;
}



int valuechange(int x,int y)
{
 int change = 0;
 change = value[temporder[x]][temporder[x+1]] - value[temporder[y]][temporder[x+1]];
 change = change + value[temporder[x-1]][temporder[x]] - value[temporder[x-1]][temporder[y]];
 change = change + value[temporder[y]][temporder[y+1]] - value[temporder[x]][temporder[y+1]];
 change = change + value[temporder[y-1]][temporder[y]] - value[temporder[y-1]][temporder[x]];
 return change;
}




void Swap(int& x,int& y)   //交換函數
{
  int temp;
  temp = x; x = y; y= temp;
}

void main()
{   
	clock_t begin,end;
	
	begin = clock();

	int  tempresult,result = 10000000;
    
	
	ifstream fin("input.txt");  //定義輸入文件
 
	fin>>n>>e;                  //輸入頂點數和邊數
    
	
	value=new int*[n+1];
	
	for(int i=0;i<=n;i++)  
		value[i] = new int[n+1];
	
	temporder = new int[n+2];
	
	int* order = new int[n+1];
	
	
	for(i=0;i<n+1;i++)
	  for(int j=0;j<n+1;j++)
	  {
	     value[i][j] = 500000;
	  }
    
	  for(i=0;i<e;i++) 
	{
	 int x,y,temp;
	 fin>>x>>y>>temp;
	 value[x][y] = temp;
	}
	
	
	  for(i=1;i<n+1;i++) 
		order[i] = i;
	
	srand((unsigned)time(NULL));
	do{ 
		for(i=1;i<n+1;i++)  temporder[i] = i;
        temporder[n+1] = 1;
	    for(i=2;i<n+1;i++) 
		{
		  int j = rand()%(n-i+1)+i;
		  Swap(temporder[i],temporder[j]);
		}
		tempresult = calculate();
	   for(i=2;i<n+1;i++)
		for(int j=2;j<n+1;j++) 
		 if(i!=j)
		  { 
			int changenum = valuechange(i,j);
			if (changenum>0) 
			{
			 Swap(temporder[i],temporder[j]);
			 tempresult = tempresult - changenum;
			}
		 }
      if(tempresult<result) 
	  {
		result = tempresult;
		for(i = 1;i<n+1;i++) order[i] = temporder[i];
	  }
	  end = clock();
   }while(end-begin<=985);

  ofstream out("output.txt"); 

      out<<result<<endl;
  
	  for(i=1;i<n+1;i++)  
	  out<<order[i]<<" ";
     
  
  
  fin.close();
  out.close();
}