#include <bits/stdc++.h>
std::istream& in = std::cin;
std::ostream& out = std::cout;
const int MaxN = 100005;
const int MaxE = MaxN << 1;
struct edge_t {
  int to, weight;
  edge_t* next;
} edges[MaxE], *cure;
inline void add_edge(edge_t** head, int u, int v, int weight = 0) {
  cure->to = v;
  cure->weight = weight;
  cure->next = head[u];
  head[u] = cure++;
}
edge_t* head[MaxN];
int d[2][MaxN], queue[MaxN], idx[MaxN];
int weight[MaxN], res[MaxN];
char s[MaxN];
std::pair<int, int> order[MaxN];
int n, m;
void bfs(int s, int* d, bool onlyZero) {
  int f = 0, b = 0, u, v;
  for (int i = 0; i < n; i++) d[i] = -1;
  queue[b++] = s;
  d[s] = 0;
  while (f != b) {
    u = queue[f++];
    for (edge_t* iter = head[u]; iter; iter = iter->next) {
      v = iter->to;
      if (d[v] == -1 && (!onlyZero || iter->weight == 0)) {
        d[v] = d[u] + 1;
        queue[b++] = v;
      }
    }
  }
}
void solve() {
  int u, v, w;
  while (in >> n >> m) {
    cure = edges;
    for (int i = 0; i < n; i++) head[i] = NULL;
    for (int i = 0; i < m; i++) {
      in >> u >> v >> w;
      add_edge(head, u, v, w);
      add_edge(head, v, u, w);
    }
    bfs(0, d[0], false);
    bfs(n - 1, d[1], true);
    int minD = n;
    for (int i = 0; i < n; i++) {
      if (d[1][i] != -1) minD = std::min(minD, d[0][i]);
      order[i] = {100, n};
    }
    int f = 0, b = 0;
    queue[b++] = 0;
    std::fill(weight, weight + n, -2);
    weight[0] = 0;
    idx[0] = 0;
    m = 1;
    for (int curD = 0; curD < minD; curD++) {
      m = 0;
      while (f < b && d[0][queue[f]] == curD) {
        u = queue[f++];
        for (edge_t* iter = head[u]; iter; iter = iter->next) {
          v = iter->to;
          if (d[0][v] == d[0][u] + 1) {
            order[v] = std::min(order[v], {iter->weight, weight[u]});
            if (weight[v] == -2) {
              idx[m++] = v;
              queue[b++] = v;
              weight[v] = -1;
            }
          }
        }
      }
      std::sort(idx, idx + m, [&](const int& a, const int& b) {
        return order[a] < order[b];
      });
      weight[idx[0]] = 0;
      for (int i = 1; i < m; i++) {
        weight[idx[i]] = order[idx[i]] != order[idx[i - 1]]
                             ? weight[idx[i - 1]] + 1
                             : weight[idx[i - 1]];
      }
    }
    int min = n;
    for (int i = 0; i < m; i++) {
      if (min != n && weight[idx[i]] != weight[min]) break;
      if (d[1][idx[i]] != -1 && (min == n || d[1][min] > d[1][idx[i]]))
        min = idx[i];
    }
    u = min;
    m = d[0][min];
    for (;;) {
      res[m++] = u;
      if (u == n - 1) break;
      for (edge_t* iter = head[u]; iter; iter = iter->next) {
        v = iter->to;
        if (d[1][v] == d[1][u] - 1 && iter->weight == 0) {
          u = v;
          break;
        }
      }
    }
    u = min;
    for (; u != 0;) {
      min = n;
      for (edge_t* iter = head[u]; iter; iter = iter->next) {
        v = iter->to;
        if (d[0][v] == d[0][u] - 1 && order[u].first == iter->weight) {
          if (min == n || weight[v] < weight[min]) {
            min = v;
            s[minD - 1 - d[0][min]] = iter->weight + '0';
          }
        }
      }
      res[d[0][min]] = min;
      u = min;
    }
    if (minD == 0) s[minD++] = '0';
    s[minD] = 0;
    out << s << std::endl;
    out << m << std::endl;
    for (int i = 0; i < m; i++) out << res[i] << " ";
    out << std::endl;
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  out.precision(16);
  solve();
  return 0;
}
