#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct node {
  int nxt, v, w;
} e[N << 1];
int n, m, head[N], cnt, pre[N], len[N], dis[N], book[N];
priority_queue<pair<int, int>, vector<pair<int, int> >,
               greater<pair<int, int> > >
    Q;
queue<int> q;
void add(int u, int v, int w) {
  e[++cnt].nxt = head[u];
  e[cnt].v = v;
  e[cnt].w = w;
  head[u] = cnt;
}
void dij(int s) {
  memset(pre, -1, sizeof pre);
  memset(dis, 0x3f, sizeof dis);
  memset(len, 0x3f, sizeof len);
  q.push(s);
  dis[s] = 0;
  len[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    Q.push(make_pair(0, u));
    for (int i = head[u]; ~i; i = e[i].nxt) {
      int v = e[i].v, w = e[i].w;
      if (dis[v] && w == 0) {
        dis[v] = 0;
        len[v] = len[u] + 1;
        pre[v] = (i ^ 1);
        q.push(v);
      }
    }
  }
  int rnk = 0, last = -1;
  while (!Q.empty()) {
    int u = Q.top().second;
    Q.pop();
    if (book[u]) continue;
    book[u] = 1;
    if (last != dis[u]) rnk++, last = dis[u];
    for (int i = head[u]; ~i; i = e[i].nxt) {
      int v = e[i].v, w = e[i].w;
      if (dis[v] > rnk * 10 + w) {
        dis[v] = rnk * 10 + w;
        len[v] = len[u] + 1;
        pre[v] = (i ^ 1);
        Q.push(make_pair(dis[v], v));
      } else if (dis[v] == rnk * 10 + w && len[v] > len[u] + 1) {
        len[v] = len[u] + 1;
        pre[v] = (i ^ 1);
      }
    }
  }
}
int main() {
  memset(head, -1, sizeof head);
  cnt = -1;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v, a;
    scanf("%d %d %d", &u, &v, &a);
    add(u + 1, v + 1, a);
    add(v + 1, u + 1, a);
  }
  dij(n);
  int c = 1;
  stack<int> s;
  while (c != n) s.push(e[pre[c]].w), c = e[pre[c]].v;
  while (!s.empty() && s.top() == 0) s.pop();
  if (s.empty())
    puts("0");
  else
    while (!s.empty()) printf("%d", s.top()), s.pop();
  putchar('\n');
  printf("%d\n", len[1]);
  c = 1;
  printf("0 ");
  while (c != n) {
    c = e[pre[c]].v;
    printf("%d ", c - 1);
  }
  return 0;
}
