#include <bits/stdc++.h>
using namespace std;
void input(int &x) {
  x = 0;
  char c = getchar();
  while ('0' > c || c > '9') c = getchar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
}
int C, head[200100], to[200100], nxt[200100], w[200100];
int q[200100], hd, tl, pa[200100], dist[200100], vis[200100], flag[200100],
    bf[200100];
struct dat {
  int len, st, pr, id;
  dat(int len = 0, int st = 0, int pr = 0, int id = 0)
      : len(len), st(st), pr(pr), id(id) {}
} pp[200100], g[200100], ans;
struct cmp {
  bool operator()(dat &a, dat &b) {
    if (a.len != b.len) return a.len > b.len;
    if (a.st != b.st) return a.st > b.st;
    return a.pr > b.pr;
  }
};
bool eq(dat &a, dat &b) {
  return a.len == b.len && a.st == b.st && a.pr == b.pr;
}
bool cmp1(dat &a, dat &b) {
  if (a.len != b.len) return a.len < b.len;
  if (a.st != b.st) return a.st < b.st;
  return a.pr < b.pr;
}
void add(int a, int b, int len) {
  ++C;
  nxt[C] = head[a];
  head[a] = C;
  to[C] = b;
  w[C] = len;
  ++C;
  nxt[C] = head[b];
  head[b] = C;
  to[C] = a;
  w[C] = len;
}
int n, m;
int f[200100], fa[200100], ga[200100], A[200100];
priority_queue<dat, vector<dat>, cmp> pq;
void bfs2() {
  pq.push(dat(0, 0, 0, 0));
  g[0] = dat(0, 0, 0, 0);
  bf[0] = 1;
  int ok = 0;
  while (!pq.empty()) {
    dat tp, t = pq.top();
    pq.pop();
    if (flag[t.id]) continue;
    flag[t.id] = 1;
    if (vis[t.id]) {
      if (!ok)
        ok = 1, ans = t;
      else {
        if (cmp1(ans, t)) break;
        if (dist[t.id] < dist[ans.id]) ans = t;
      }
    }
    int ll = t.len + 1;
    if (!f[ll] || (f[ll] && !eq(pp[ll], t))) f[ll]++;
    pp[ll] = t;
    for (int i = head[t.id]; i; i = nxt[i]) {
      int x = to[i];
      if (flag[x]) continue;
      tp = dat(ll, w[i], f[ll], x);
      if (!bf[x] || cmp1(tp, g[x])) {
        pq.push(tp);
        bf[x] = 1;
        g[x] = tp;
        fa[x] = t.id;
        ga[x] = w[i];
      }
    }
  }
  int k = ans.id, ca = 0;
  while (k) {
    A[++ca] = k;
    printf("%d", ga[k]);
    k = fa[k];
  }
  puts("");
  printf("%d\n", ans.len + dist[ans.id]);
  printf("0");
  while (ca) printf(" %d", A[ca--]);
  k = ans.id;
  while (k != n - 1) {
    k = pa[k];
    printf(" %d", k);
  }
  puts("");
}
void bfs1() {
  q[tl++] = n - 1;
  vis[n - 1] = 1;
  pa[n - 1] = -1;
  dist[n - 1] = 1;
  while (hd < tl) {
    int t = q[hd++];
    for (int i = head[t]; i; i = nxt[i]) {
      int x = to[i];
      if (vis[x] || w[i]) continue;
      q[tl++] = x;
      vis[x] = 1;
      pa[x] = t;
      dist[x] = dist[t] + 1;
    }
  }
}
int main() {
  input(n);
  input(m);
  for (int a, b, c, i = 0; i < m; i++) {
    input(a);
    input(b);
    input(c);
    add(a, b, c);
  }
  bfs1();
  if (vis[0]) {
    puts("0");
    printf("%d\n%d", dist[0], 0);
    int x = 0;
    while (x != n - 1) {
      x = pa[x];
      printf(" %d", x);
    }
    puts("");
    return 0;
  }
  bfs2();
  return 0;
}
