using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
class Example
{ static int nv,ne;              // вхідні дані з першого рядка
  static int [] l = new int [9]; // оцінка довжини
  static int [] p = new int [9]; // попередники
  static List<List<int>> b = new List<List<int>>();// списки суміжності
  static List<List<int>> w = new List<List<int>>();// ваги ребер   
  static bool[] c = new bool[9]; // ознака сталості

  static int step (int j)
  { int i,k,
          s,        // оцінка довжини,
    l_max=99999999; // верхня межа довжини шляху
    for (i=0; i<b[j].Count; i++)
    { int bji = b[j][i];
      if   (!c[bji])
      { s= l[j] + w[j][i];
        if (l[bji] > s)
        { l[bji] = s;
          p[bji] = j;
        }
      }
    }
    s=l_max;
    for (k=0; k<nv; k++)
    if (!c[k]) if (s>l[k])
    { s=l[k];
      i=k;
    }
    c[i]=true;
    return i;
  }

  public static void Main()
  { try
    { int u,  // зчитана вага ребра
      i,j,k;  // лічильники
      using (StreamReader file = new StreamReader("input.txt"))
      { string[] s = file.ReadLine().Split(' ');
        nv = Int32.Parse(s[0]);
        ne = Int32.Parse(s[1]);
        for (j=0; j<nv; j++)
        { b.Add(new List<int>());
          w.Add(new List<int>());
          l[j]=999999;
          c[j]=false;
          p[j]=0;
        }
        for (i=0; i<ne; i++)
        { s = file.ReadLine().Split(' ');
          j = Int32.Parse(s[0]);
          k = Int32.Parse(s[1]);
          u = Int32.Parse(s[2]);
          b[j].Add(k);  w[j].Add(u);
          b[k].Add(j);  w[k].Add(u);
        }
        int start = 0,    // Номери вершини,
           finish = nv-1; // між якими шукаємо шлях
        c[start]=true;
        l[start]=0;
        j=start;
        while (j!=finish) j=step(j);
        string answer = Convert.ToString(l[finish])+"\n"
                      + Convert.ToString(finish);
        j=finish;
        while (j!=start)
        { j=p[j];
          answer+=" "+Convert.ToString(j);
        }
        File.WriteAllText ("output.txt",answer);
      }
    }
    catch (Exception e) {Console.WriteLine(e.Message);}
  }
}