#include <bits/stdc++.h>
using namespace std;
int n, m, fro[100009], frov[100009], dis[100009], prt[100009], Len[100009],
    ret[100009];
int hd[100009], to[100009 << 1], nxt[100009 << 1], w[100009 << 1], cnt = 0;
struct DT {
  int u, va, len;
  friend bool operator<(DT x, DT y) {
    return x.va == y.va ? x.len > y.len : x.va > y.va;
  }
};
priority_queue<DT> q;
queue<int> sq;
int read();
void add(int u, int v, int _w) {
  to[++cnt] = v;
  nxt[cnt] = hd[u];
  hd[u] = cnt;
  w[cnt] = _w;
}
void bfs() {
  while (sq.size()) {
    int u = sq.front();
    sq.pop();
    int ok = true;
    for (int i = hd[u], v; i; i = nxt[i])
      if (dis[v = to[i]] && (!w[i])) {
        dis[v] = 0;
        sq.push(v);
        fro[v] = u;
        frov[v] = 0;
        Len[v] = Len[u] + 1;
        q.push((DT){v, 0, Len[v]});
      }
  }
}
void dijk() {
  for (int i = 1; i <= n; ++i) dis[i] = 1047483647;
  dis[n] = 0;
  q.push((DT){n, 0, 0});
  cnt = 0;
  Len[n] = 0;
  sq.push(n);
  bfs();
  while (q.size()) {
    int u = q.top().u, nva = q.top().va, nl = q.top().len;
    q.pop();
    if (dis[u] < nva) continue;
    if (cnt && dis[u] == ret[cnt])
      dis[u] = cnt;
    else {
      ret[++cnt] = dis[u];
      dis[u] = cnt;
    }
    for (int i = hd[u], v; i; i = nxt[i])
      if (dis[v = to[i]] > (dis[u] * 10 + w[i])) {
        dis[v] = dis[u] * 10 + w[i];
        q.push((DT){v, dis[v], nl + 1});
        fro[v] = u;
        frov[v] = w[i];
      }
  }
}
int main() {
  n = read(), m = read();
  for (int i = 1, u, v, _w; i <= m; ++i)
    u = read() + 1, v = read() + 1, _w = read(), add(u, v, _w), add(v, u, _w);
  dijk();
  int nu = 1, sn = 0;
  while (nu != n) {
    prt[++sn] = frov[nu];
    nu = fro[nu];
  }
  bool noind = true;
  for (int i = sn; i; --i)
    if (noind && (!prt[i]))
      continue;
    else
      noind = false, printf("%d", prt[i]);
  if (noind) printf("0");
  printf("\n%d\n", sn + 1);
  nu = 1;
  while (nu != n) {
    printf("%d ", nu - 1);
    nu = fro[nu];
  }
  printf("%d\n", n - 1);
  return 0;
}
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') f = (c == '-') ? -1 : f, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
