#include <bits/stdc++.h>
const int MAXN = 2e5, MAXM = 2e5;
int n, m, ecnt, head[MAXN + 5], d[MAXN + 5], suf[MAXN + 5];
bool vis[MAXN + 5];
std::vector<int> curp, nxtp;
std::queue<int> que;
struct Edge {
  int to, cst, nxt;
} graph[MAXM * 2 + 5];
inline void link(const int s, const int t, const int c) {
  graph[++ecnt] = {t, c, head[s]};
  head[s] = ecnt;
}
inline void initReach() {
  for (int i = 1; i <= n; ++i) d[i] = -1;
  d[1] = 0, que.push(1);
  for (int u; !que.empty();) {
    u = que.front(), que.pop();
    for (int i = head[u], v; i; i = graph[i].nxt) {
      if (!~d[v = graph[i].to]) {
        d[v] = d[u] + 1, que.push(v);
      }
    }
  }
}
inline int zeroReach() {
  int mind = d[n];
  curp.push_back(n), vis[n] = true;
  for (int cur = 0; cur ^ curp.size(); ++cur) {
    int u = curp[cur];
    for (int i = head[u], v; i; i = graph[i].nxt) {
      if (!vis[v = graph[i].to] && !graph[i].cst) {
        curp.push_back(v), vis[v] = true, suf[v] = u;
        if (mind > d[v]) mind = d[v];
      }
    }
  }
  return mind;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1, u, v, w; i <= m; ++i) {
    scanf("%d %d %d", &u, &v, &w), ++u, ++v;
    link(u, v, w), link(v, u, w);
  }
  initReach();
  int dist = zeroReach();
  bool zero = true;
  for (int l = dist; l; --l) {
    int dig = 10;
    for (int u : curp) {
      for (int i = head[u], v; i; i = graph[i].nxt) {
        if (d[v = graph[i].to] + 1 == l && graph[i].cst < dig) {
          dig = graph[i].cst;
        }
      }
    }
    if (dig) zero = false;
    if (l == 1 || !zero) putchar(dig ^ '0');
    for (int u : curp) {
      for (int i = head[u], v; i; i = graph[i].nxt) {
        if (d[v = graph[i].to] + 1 == l && graph[i].cst == dig && !vis[v]) {
          vis[v] = true, nxtp.push_back(v), suf[v] = u;
        }
      }
    }
    curp = nxtp, nxtp.clear();
  }
  if (zero) putchar('0');
  int ans = 1, u;
  for (u = 1; u ^ n; ++ans, u = suf[u])
    ;
  printf("\n%d\n0", ans), u = 1;
  do printf(" %d", (u = suf[u]) - 1);
  while (u ^ n);
  putchar('\n');
  return 0;
}
