#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
struct edge {
  int v, nex, cost;
} e[maxn * 2];
int ee, p[maxn];
void add(int u, int v, int c) {
  e[ee].v = v;
  e[ee].nex = p[u];
  e[ee].cost = c;
  p[u] = ee++;
}
int dist[maxn];
void bfs1() {
  memset(dist, -1, sizeof(dist));
  queue<int> q;
  q.push(0);
  dist[0] = 0;
  int s, v;
  while (!q.empty()) {
    s = q.front();
    q.pop();
    for (v = p[s]; ~v; v = e[v].nex) {
      if (dist[e[v].v] != -1) continue;
      dist[e[v].v] = dist[s] + 1;
      q.push(e[v].v);
    }
  }
}
int d[maxn];
void bfs2(int s) {
  queue<int> q;
  q.push(s);
  int u, v;
  for (u = 0; u < s; u++) d[u] = maxn;
  d[s] = 1;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (v = p[u]; ~v; v = e[v].nex) {
      if (e[v].cost != 0) continue;
      if (d[e[v].v] > d[u] + 1) {
        d[e[v].v] = d[u] + 1;
        q.push(e[v].v);
      }
    }
  }
}
bool zero;
int mn[maxn];
int main() {
  int n, m, i, a, b, c, j, v, u;
  cin >> n >> m;
  memset(p, -1, sizeof(p));
  for (i = 1; i <= m; i++) {
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
    add(b, a, c);
  }
  bfs1();
  bfs2(n - 1);
  int md = maxn + 10;
  for (i = 0; i < n; i++)
    if (d[i] != maxn) md = min(md, dist[i]);
  vector<int> now, after;
  for (i = 0; i < n; i++)
    if (d[i] != maxn && dist[i] == md) now.push_back(i);
  zero = false;
  for (i = md; i > 0; i--) {
    mn[i] = 10;
    for (j = 0; j < now.size(); j++) {
      u = now[j];
      for (v = p[u]; ~v; v = e[v].nex) {
        if (dist[e[v].v] + 1 == dist[u]) mn[i] = min(mn[i], e[v].cost);
      }
    }
    printf("%d", mn[i]);
    zero = true;
    after.clear();
    for (j = 0; j < now.size(); j++) {
      u = now[j];
      for (v = p[u]; ~v; v = e[v].nex) {
        if (e[v].cost == mn[i] && dist[e[v].v] + 1 == dist[u]) {
          if (d[e[v].v] == maxn) after.push_back(e[v].v);
          d[e[v].v] = min(d[e[v].v], d[u] + 1);
        }
      }
    }
    now = after;
  }
  if (!zero) cout << '0';
  cout << endl << d[0] << endl;
  int cur = 0;
  for (i = 1; i <= d[0]; i++) {
    printf("%d ", cur);
    for (v = p[cur]; ~v; v = e[v].nex) {
      if (d[cur] == d[e[v].v] + 1 && e[v].cost == mn[i]) {
        cur = e[v].v;
        break;
      }
    }
  }
  cout << endl;
}
