#include <bits/stdc++.h>
using namespace std;
void readline(char *s) {
  int len = 0;
  char c;
  for (c = ((char)fgetc(stdin)); c != '\n';
       s[len++] = c, c = ((char)fgetc(stdin)))
    ;
  s[len] = 0;
}
void readstr(char *s) {
  int len = 0;
  char c;
  for (c = ((char)fgetc(stdin)); c != ' ' && c != '\n';
       s[len++] = c, c = ((char)fgetc(stdin)))
    ;
  s[len] = 0;
}
void printstr(const char *s) {
  int len = strlen(s);
  for (int(i) = (0); (i) <= (len - 1); i++) fputc((s[i]), stdout);
}
void to_lower(char *s, int L, int R) {
  for (int(i) = (L); (i) <= (R); i++)
    if (((s[i]) >= 'A' && (s[i]) <= 'Z')) s[i] = s[i] - 'A' + 'a';
}
void to_upper(char *s, int L, int R) {
  for (int(i) = (L); (i) <= (R); i++)
    if (((s[i]) >= 'a' && (s[i]) <= 'z')) s[i] = s[i] - 'a' + 'A';
}
long long readll() {
  char c;
  long long ans = 0, x = 1;
  for (c = ((char)fgetc(stdin)); !((c) >= '0' && (c) <= '9') && c != '-';
       c = ((char)fgetc(stdin)))
    ;
  if (c == '-') x = -1, c = ((char)fgetc(stdin));
  for (; ((c) >= '0' && (c) <= '9');
       ans = ans * 10 + c - '0', c = ((char)fgetc(stdin)))
    ;
  return ans * x;
}
void printll(long long x) {
  int a[25], cnt = 0;
  if (x == 0) {
    fputc(('0'), stdout);
    return;
  }
  if (x < 0) fputc(('-'), stdout), x = -x;
  for (; x; a[cnt++] = x - x / 10 * 10, x /= 10)
    ;
  for (int(i) = (cnt - 1); (i) >= (0); i--) fputc((a[i] + '0'), stdout);
}
int n, m, dis[100005], zdis[100005], zpar[100005], par[100005], dispar[100005];
struct edge {
  int to, len;
  edge(int x, int y) {
    to = x;
    len = y;
  }
};
vector<edge> g[100005];
int que[100005], l, r;
void bfs(int start) {
  l = r = 0;
  que[r++] = start;
  memset(dis, -1, sizeof(dis));
  dis[start] = 0;
  while (l < r) {
    int x = que[l++];
    for (int(i) = (0); (i) <= ((int)g[x].size() - 1); i++) {
      int y = g[x][i].to, l = g[x][i].len;
      if (!~dis[y]) {
        dis[y] = dis[x] + 1;
        que[r++] = y;
      }
    }
  }
  for (int(i) = (1); (i) <= (n); i++)
    if (!~dis[i]) dis[i] = 1000000007;
}
void zbfs(int start, vector<int> &v) {
  l = r = 0;
  que[r++] = start;
  memset(zdis, -1, sizeof(zdis));
  zdis[start] = 0;
  while (l < r) {
    int x = que[l++];
    v.push_back(x);
    for (int(i) = (0); (i) <= ((int)g[x].size() - 1); i++) {
      int y = g[x][i].to, l = g[x][i].len;
      if (l) continue;
      if (!~zdis[y]) {
        zpar[y] = x;
        zdis[y] = zdis[x] + 1;
        que[r++] = y;
      }
    }
  }
}
int v[100005], vcnt, nw[100005], nwcnt;
int main() {
  n = ((int)readll()), m = ((int)readll());
  for (int(i) = (1); (i) <= (m); i++) {
    int x = ((int)readll()), y = ((int)readll()), z = ((int)readll());
    g[x].push_back(edge(y, z));
    g[y].push_back(edge(x, z));
  }
  vector<int> zero;
  zbfs(n - 1, zero);
  bfs(0);
  int minlen = 2000000007;
  for (int(i) = (0); (i) <= ((int)zero.size() - 1); i++)
    minlen = min(minlen, dis[zero[i]]);
  for (int(i) = (0); (i) <= ((int)zero.size() - 1); i++)
    if (dis[zero[i]] == minlen) v[vcnt++] = (zero[i]);
  bool iszero = true;
  while (v[0] != 0) {
    iszero = false;
    nwcnt = 0;
    int minedge = 100;
    for (int(i) = (0); (i) <= (vcnt - 1); i++) {
      for (int(j) = (0); (j) <= ((int)g[v[i]].size() - 1); j++) {
        if (dis[g[v[i]][j].to] < dis[v[i]])
          minedge = min(minedge, g[v[i]][j].len);
      }
    }
    fputc((minedge + '0'), stdout);
    int minlen = 2000000007;
    for (int(i) = (0); (i) <= (vcnt - 1); i++) {
      for (int(j) = (0); (j) <= ((int)g[v[i]].size() - 1); j++) {
        if (dis[g[v[i]][j].to] < dis[v[i]] && g[v[i]][j].len == minedge) {
          int x = g[v[i]][j].to;
          int xx = dispar[v[i]] + 1;
          minlen = min(minlen, xx);
          if (!par[x] || xx < dispar[x]) {
            dispar[x] = xx;
            par[x] = v[i];
          }
        }
      }
    }
    for (int(i) = (0); (i) <= (vcnt - 1); i++)
      for (int(j) = (0); (j) <= ((int)g[v[i]].size() - 1); j++) {
        if (dis[g[v[i]][j].to] < dis[v[i]] && dispar[g[v[i]][j].to] == minlen)
          nw[nwcnt++] = (g[v[i]][j].to);
      }
    sort(nw, nw + nwcnt);
    nwcnt = unique(nw, nw + nwcnt) - nw;
    vcnt = nwcnt;
    for (int(i) = (0); (i) <= (vcnt - 1); i++) v[i] = nw[i];
  }
  if (iszero) fputc(('0'), stdout);
  fputc(('\n'), stdout);
  vector<int> ans;
  ans.push_back(0);
  int i = 0;
  while (zdis[i] == -1 && par[i]) {
    i = par[i];
    ans.push_back(i);
  }
  while (i != n - 1) {
    i = zpar[i];
    ans.push_back(i);
  }
  printll((long long)(ans.size()));
  fputc(('\n'), stdout);
  for (int(i) = (0); (i) <= ((int)ans.size() - 1); i++) {
    printll((long long)(ans[i]));
    fputc((i + 1 == ans.size() ? '\n' : ' '), stdout);
  }
  return 0;
}
