#include <cstdio>
#include <memory>
#include <deque>
#include <limits>
#include <fstream>
#include <math.h>
using namespace std;
const int MAX = 500;

int source,dest,n;
int counter=0;
int Cmax=0;
int k=0;
int kk=0;
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 z)
{
  int i,First;
  q.push_front(v);
  while(!q.empty())
  {
     First = q[0];
     if (First == dest) return;
     q.pop_front();
     used[First] = 1;
     for(i=0;i<n;i++)
     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;

    	for (int i=0; i<n; i++){
			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;
  source=0;
  dest=n-1;
   MaxFlow = 0;
  for (int i=0; i<M; ++i)
  {

	  in >>a>>b>>c;
	  m[a-1][b-1] = c;
	  if (c< Cmax) c=Cmax;
  }

  for (int i=Cmax; i>0; i/=2) {
	kk++;
  }
kk+=1;
for (int i=0; i<kk; i++) {
	k*=2;
  }




  for (int i = kk; i >0; i /= 2) {
	  while (1)
	  {
		q.clear();
		memset(p,-1,sizeof(p));
		memset(used,0,sizeof(used));
		memset(color,0,sizeof(color));
		bfs(source,i);
		flow = FindFlow(dest); if (flow == INT_MAX) break;
		MaxFlow += flow;
		Rebuild(dest,flow);
	  }
  }
  /*


  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;




}