#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int s = 0;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  do {
    s = s * 10 + c - '0';
  } while ((c = getchar()) >= '0' && c <= '9');
  return s;
}
const int N = 100010;
int n, m, tot, s[N], l[N], l0[N], fr0[N], fr[N], h[N], ans[N], ansp;
struct eg {
  int dt, w, nx;
} e[N * 2];
queue<int> q, qa[2][10];
bool inq[N], inq0[N], z[N];
void link(int aa, int bb, int ww) {
  e[++tot].nx = h[aa];
  e[tot].dt = bb;
  e[tot].w = ww;
  h[aa] = tot;
  e[++tot].nx = h[bb];
  e[tot].dt = aa;
  e[tot].w = ww;
  h[bb] = tot;
}
void zerobfs() {
  q.push(n - 1);
  fr0[n - 1] = -1;
  inq0[n - 1] = 1;
  while (!q.empty()) {
    int hn = q.front();
    q.pop();
    for (int nx, pt = h[hn]; pt; pt = e[pt].nx)
      if (!e[pt].w && !inq0[nx = e[pt].dt])
        q.push(nx), inq0[nx] = 1, fr0[nx] = hn, l0[nx] = l0[hn] + 1;
  }
}
void bfs() {
  qa[0][0].push(0);
  memset(s, 0x7f, sizeof s);
  memset(l, 0x7f, sizeof l);
  s[0] = 0;
  l[0] = 0;
  fr[0] = -1;
  z[0] = 1;
  int curp = 1;
  while (1) {
    curp ^= 1;
    while (!q.empty()) {
      int hn = q.front();
      q.pop();
      if (!inq[hn]) qa[curp][s[hn]].push(hn), inq[hn] = 1;
    }
    bool flag = 1;
    for (int i = 0; i <= 9; i++) {
      while (!qa[curp][i].empty()) {
        int hn = qa[curp][i].front();
        qa[curp][i].pop();
        flag = 0;
        for (int nx, pt = h[hn]; pt; pt = e[pt].nx) {
          nx = e[pt].dt;
          if (l[hn] + 1 < l[nx] || (l[hn] + 1 == l[nx] && (e[pt].w < s[nx]))) {
            s[nx] = e[pt].w, l[nx] = l[hn] + 1, fr[nx] = hn;
            if (!inq[nx]) q.push(nx);
          }
        }
      }
    }
    if (flag) break;
  }
}
int main() {
  int i, j = 0;
  n = read();
  m = read();
  for (i = 1; i <= m; i++) {
    int aa = read(), bb = read();
    link(aa, bb, read());
  }
  zerobfs();
  bfs();
  ansp = n - 1;
  for (i = 0; i < n; i++)
    if (inq0[i])
      if (l[i] < l[ansp] || (l[i] == l[ansp] && s[i] < s[ansp]) ||
          (l[i] == l[ansp] && s[i] == s[ansp] &&
           l[i] + l0[i] < l[ansp] + l0[ansp]))
        ansp = i;
  for (i = ansp; i != n - 1; i = fr0[i]) fr[fr0[i]] = i, s[fr0[i]] = 0;
  bool flag = 0;
  for (i = n - 1; i; i = fr[i]) {
    if (flag || s[i]) putchar('0' + s[i]), flag = 1;
    ans[++j] = i;
  }
  if (!flag) putchar('0');
  printf("\n%d\n", l[ansp] + l0[ansp] + 1);
  ans[++j] = 0;
  for (i = j; i > 1; i--) printf("%d ", ans[i]);
  printf("%d\n", ans[1]);
  return 0;
}
