#include <cstdio>
#include <memory>
#include <deque>
#include <limits>
#include <fstream>
#include <vector>


using namespace std;
const int MAX = 500;
const int AAA=1000000000;
int source,dest,n;
int z=0;
int counter=0;
int Cmax=0;
vector< vector<int> > W( MAX );
deque<int> q;
int answer[MAX];
int m[MAX][MAX];
int used[MAX],p[MAX];
int color[MAX];

int min(int i, int j)
{
  return (i < j) ? i : j;
}


void bfs(int v)
{
  int First;
  q.push_front(v);
  while(!q.empty())
  {
     First = q[0];
     if (First == dest) return;
     q.pop_front();
     used[First] = 1;
	   int s=W[First].size();

     for(int ii=0;ii<s;ii++)
	 {
		 int i=W[First][ii];
		 if ((((m[First][i])) > 0) && (!used[i]))
		 {
			 p[i] = First;
			 q.push_back(i);
		 }
	 }
  }
}



void Rebuild(int k, int flow)
{
  if (p[k] == -1) return;
  Rebuild(p[k],flow);
  m[p[k]][k] -= flow;
  m[k][p[k]] += flow;
}





int FindFlow(int k)
{
  int x;
  if (p[k] == -1) return INT_MAX;
  x = FindFlow(p[k]);
  return min(x,m[p[k]][k]);
}
void DFSVISIT(int a) {
	color[a]=1;

    	int s=W[a].size();
    	for (int ii=0; ii<s; ii++){
			int i;
			i=W[a][ii];
			if (m[a][i]!=0) {


    			if (color[i]==0) {
    			//	pr[ii]=a;
    				DFSVISIT(i);
    			}
			}
    	}
    	color[a]=2;


    	answer[counter]=a;
    	counter++;
}


void main(void)
{
  int a,b,c;
  int M;
  int MaxFlow,flow;
  std::ifstream in("cut.in");
  std::ofstream out("cut.out");

  memset(m,0,sizeof(m));

  in>>n>>M;
 memset(color,0,sizeof(color));
  source=0;
  dest=n-1;
   MaxFlow = 0;
  for (int i=0; i<M; ++i)
  {

	  in >>a>>b>>c;
	  m[a-1][b-1] = c;
	    m[b-1][a-1] = c;
	    W[a-1].push_back(b-1);
		W[b-1].push_back(a-1);

	  if (c> Cmax) Cmax=c;
  }

int k = 1;
               while (k << 1 <= Cmax) {
                       k <<= 1;
               }



  /*for (int i = k; i >0; i >>= 1) {
	  z+=i;*/
	  while (1)
	  {
		q.clear();
		memset(p,-1,sizeof(p));
		memset(used,0,sizeof(used));
		memset(color,0,sizeof(color));
		bfs(source);
		flow = FindFlow(dest); if (flow > AAA) break;
		MaxFlow += flow;
		Rebuild(dest,flow);
	  }
	 // out<< z<< " ";
 // }
  for (int i=0; i<n; i++) {
	  W[i].clear();
  }
  for (int i=0; i<n; i++) {
	  for (int j=0; j<n; j++) {
		  if (m[i,j]!=0) {
			 W[i].push_back(j);
		  }
	 }

  }
  /*for (int i=0; i< n; i++)
  {
	  for (int j=0; j<n; j++) {

		out << m[i][j]<< " ";
	  }
	  out<< "\n";
  }*/
  DFSVISIT (0);
  out<<counter<<"\n";
  for (int i=0; i<counter-1;i++){ out << answer[i]+1<< " ";}
  out << answer[counter-1]+1;




}