package work;
import java.util.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
public class Work
{ static int nv,ne;       // вхідні дані з першого рядка
  static int [] l = new int[9];          // оцінка довжини
  static int [] p = new int[9];          // попередники
  static boolean [] c = new boolean[9];  // ознака сталості
  static LinkedList b = new LinkedList();// списки суміжності
  static LinkedList w = new LinkedList();// ваги ребер

  public static void main(String args[])
  { int
    u,               // зчитана вага ребра
    i,j,k;           // лічильники
        try 
    { FileReader in      = new FileReader( "input.txt");
      FileWriter out     = new FileWriter("output.txt");
      BufferedReader bin = new BufferedReader(in);
      Scanner         sc = new Scanner(bin);
      nv = sc.nextInt();
      ne = sc.nextInt();
      for (j=0; j<nv; j++)
      { b.add(new LinkedList());
        w.add(new LinkedList());
        l[j]=999999;
        c[j]=false;
        p[j]=0;
      }
      for (i=0; i<ne; i++)
      { j = sc.nextInt();
        k = sc.nextInt();
        u = sc.nextInt();
        ((LinkedList) b.get(j)).add(k);
        ((LinkedList) w.get(j)).add(u);
        ((LinkedList) b.get(k)).add(j);
        ((LinkedList) w.get(k)).add(u);
      }
      in.close();
      int start = 0,    // Номери вершини,
         finish = nv-1; // між якими шукаємо шлях
      c[start]=true;
      l[start]=0;
      j=start;
      while (j!=finish) j=step(j);
      out.write(l[finish]+"\n"+finish);
      j=finish;
      while (j!=start)
      { j=p[j];
        out.write(" "+j);
      }
      out.write("\n");
      out.close();
    }
    catch (IOException e) {}
  }

  static int step (int j)
  { int i,k,
          s,        // оцінка довжини,
    l_max=99999999; // верхня межа довжини шляху
    for (i=0; i<((LinkedList) b.get(j)).size(); i++)
    { int bji = (int) ((LinkedList) ((LinkedList) b.get(j))).get(i);
      if   (!c[bji])
      { s= l[j]+(int) ((LinkedList) ((LinkedList) w.get(j))).get(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;
  }
}