#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> g[100500];
vector<int> c[100500];
bool used[100500];
bool ok[100500];
int d[100500];
int p[100500], pk[100500];
int leng[100500];
int q[300500];
int ql, qr;
void dfs(int x) {
  ok[x] = 1;
  memset(leng, 63, sizeof leng);
  leng[x] = 0;
  ql = 0, qr = 0;
  q[qr++] = x;
  while (ql < qr) {
    x = q[ql];
    ql++;
    ok[x] = 1;
    for (int i = 0; i < g[x].size(); ++i) {
      if (leng[g[x][i]] > 100500 && c[x][i] == 0) {
        leng[g[x][i]] = leng[x] + 1;
        p[g[x][i]] = x;
        pk[g[x][i]] = c[x][i];
        q[qr++] = g[x][i];
      }
    }
  }
}
int qw[300500], qwl, qwr;
void bfs(int x) {
  qwl = qwr = 0;
  qw[qwr++] = x;
  memset(d, 63, sizeof d);
  d[x] = 0;
  while (qwl < qwr) {
    x = qw[qwl];
    qwl++;
    for (int i = 0; i < g[x].size(); ++i) {
      if (d[g[x][i]] > 100500) {
        qw[qwr++] = g[x][i];
        d[g[x][i]] = d[x] + 1;
      }
    }
  }
}
int v[200500];
void bfs2() {
  ql = qr = 0;
  int mn = 1 << 30;
  for (int i = 0; i < n; i++)
    if (ok[i] && d[i] < mn) mn = d[i];
  for (int i = 0; i < n; i++)
    if (ok[i] && d[i] == mn) q[qr++] = i;
  int sz = 0;
  while (ql < qr) {
    sz = 0;
    v[sz++] = q[ql];
    ql++;
    while (ql < qr && d[q[ql]] == d[v[0]]) {
      v[sz++] = q[ql];
      ql++;
    }
    bool ok2 = false;
    for (int k = 0; k < 10 && !ok2; ++k) {
      for (int i = 0; i < sz; ++i) {
        int x = v[i];
        for (int j = 0; j < g[x].size(); ++j) {
          if (c[x][j] == k && d[g[x][j]] < d[x]) {
            q[qr++] = g[x][j];
            if (leng[g[x][j]] > 100500) {
              p[g[x][j]] = x;
              pk[g[x][j]] = k;
            }
            ok2 = true;
          }
        }
      }
    }
  }
}
int bans[100500], bsz = 0;
int ans[100500];
int asz = 0;
void dfs2(int x, int k = 0) {
  if (k == asz) {
    bans[bsz++] = x;
    return;
  }
  for (int i = 0; i < g[x].size(); ++i) {
    if (d[g[x][i]] > d[x] && c[x][i] == ans[asz - k - 1] &&
        leng[g[x][i]] < leng[x]) {
      dfs2(g[x][i], k + 1);
    }
  }
}
int cnt = 0;
bool out = 0;
vector<int> output;
void rec(int x) {
  if (x == n - 1) return;
  rec(p[x]);
  if (!ok[x]) {
    cout << pk[x];
    ans[asz++] = pk[x];
    ++cnt;
    out = true;
  }
}
void rec2(int x, int j = 0) {
  if (x == 0) {
    output.push_back(0);
    return;
  }
  for (int i = 0; i < g[x].size(); i++) {
    if (d[g[x][i]] < d[x] && c[x][i] == ans[j]) {
      rec2(g[x][i], j + 1);
      break;
    }
  }
  output.push_back(x);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    int f, t, l;
    scanf("%d%d%d", &f, &t, &l);
    g[f].push_back(t);
    c[f].push_back(l);
    g[t].push_back(f);
    c[t].push_back(l);
  }
  dfs(n - 1);
  bfs(0);
  bfs2();
  rec(0);
  dfs2(0);
  int x = bans[0];
  for (int i = 1; i < bsz; ++i) {
    if (leng[bans[i]] < leng[x]) x = bans[i];
  }
  if (!out) cout << 0;
  cout << endl;
  rec2(x);
  x = p[x];
  while (x) {
    output.push_back(x);
    x = p[x];
  }
  cout << output.size() << endl;
  for (int i = 0; i < output.size(); i++) cout << output[i] << " ";
}
