#include <iostream>
#include <fstream>
#include <queue>


using namespace std;

const int MAXN = 10000; // max. num. di nodo

struct arco {
  int nodo, peso;  // nodo destinazione e peso
};

struct nodoDist {
  int nodo, dist; // numero del nodo e distanza dall'origine
  nodoDist(int n, int d) {nodo = n; dist = d;}
  bool operator<(const nodoDist x) const {return x.dist < dist; }
};
  

int n, m;

arco adiacenti[MAXN][MAXN];
priority_queue<nodoDist> pq;

int grado[MAXN];  
int dist[MAXN]; //dist[i] � la lungh. del camm. minimo al nodo i;
int padre[MAXN]; // genitore nel cammino minimo
bool visit[MAXN];

int inizio = 0, fine = n-1;

void dijkstra() {
  dist[inizio] = 0;
  padre[inizio] = -1;
  for(int i = 0; i < n; i++) {
    pq.push(nodoDist(i, dist[i]));
  }
  while(!pq.empty()) {
    int u = pq.top().nodo;
    pq.pop();
    if(visit[u]) continue;
    visit[u] = true;
    for(int j = 0; j < grado[u]; j++) {
      arco a = adiacenti[u][j];
      int v = a.nodo;
      int d = dist[u] + a.peso;
      if(d < dist[v]) {
        pq.push(nodoDist(v, d));
        dist[v] = d;
        padre[v] = u;
      }               
    }
  }
}
  
int main() {
	ifstream fin("input13.txt");
	ofstream fout("output.txt");
	fin >> n >> m;
	
	for(int i = 0; i < n; i++) {
    grado[i] = 0;
    dist[i] = INT_MAX;
    visit[i] = false;
  }
    
  for(int i = 0; i < m; i++) {
    int x, y, p;
    fin >> x >> y >> p;
    x--; y--;  // nell'input i nodi sono numerati da 1
    int k = grado[x]++;
    adiacenti[x][k].nodo = y;
    adiacenti[x][k].peso = p;
  }
  
  inizio = 0;
  fine = n-1;
  
  dijkstra();
  cout << dist[fine] << endl;  
  //fout << dist[fine] << endl; 


 /* int u = fine; 
  while(u != -1) {
    cout << u+1 << " ";
    u = padre[u];
  }
  cout << endl;
 */
  
  int path[n];
  int k = 0;
  int u = fine;
  while(u != -1) {
    path[k++] = u;
    u = padre[u];
  } // cammino al contrario
  cout << endl;
  
  for(int i = k-1; i >= 0; i--)
    cout << path[i]+1 << " ";  
  system("PAUSE"); 	
}