#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[100001];
int zero_len[100001];
int d[100001];
int pp[100001], mn[100001], ppz[100001];
int visited[100001];
void bfs_zero(int s, int *dd) {
  queue<int> q;
  dd[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int k = q.front();
    q.pop();
    for (auto &i : v[k]) {
      if (dd[i.first] == -1 && i.second == 0) {
        dd[i.first] = dd[k] + 1;
        ppz[i.first] = k;
        q.push(i.first);
      }
    }
  }
}
int bfs_non_zero(int s, int *dd) {
  int len = 1 << 30;
  queue<int> q;
  dd[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int k = q.front();
    q.pop();
    for (auto &i : v[k]) {
      if (dd[i.first] == -1) {
        dd[i.first] = dd[k] + 1;
        pp[i.first] = k;
        mn[i.first] = i.second;
        if (zero_len[i.first] == -1)
          q.push(i.first);
        else
          len = min(len, dd[i.first]);
      } else if (dd[i.first] == dd[k] + 1 && i.second < mn[i.first]) {
        pp[i.first] = k;
        mn[i.first] = i.second;
      }
    }
  }
  return len;
}
inline void getd(int &d) {
  char ch;
  while (!isdigit(ch = getchar()))
    ;
  d = 0;
  do {
    (d *= 10) += ch - '0';
  } while (isdigit(ch = getchar()));
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  while (m--) {
    int x, y, w;
    getd(x), getd(y), getd(w);
    v[x].push_back(make_pair(y, w));
    v[y].push_back(make_pair(x, w));
  }
  for (int i = 0; i < n; ++i) zero_len[i] = pp[i] = ppz[i] = -1;
  bfs_zero(n - 1, zero_len);
  for (int i = 0; i < n; ++i) d[i] = -1, mn[i] = 10;
  int len = bfs_non_zero(0, d);
  queue<int> qq;
  int zn = 1 << 30, nx = 10;
  for (int i = 0; i < n; ++i) {
    if (len == d[i] && zero_len[i] != -1) {
      if (mn[i] < nx || mn[i] == nx && zn > zero_len[i]) {
        nx = mn[i];
        zn = zero_len[i];
        while (!qq.empty()) qq.pop();
        qq.push(i);
      } else if (mn[i] == nx && zn == zero_len[i])
        qq.push(i);
    }
  }
  for (int i = 0; i < n; ++i) pp[i] = -1, visited[i] = 0;
  while (len--) {
    queue<int> ww;
    putchar(nx + '0');
    int pre_nx = nx;
    nx = 10;
    while (!qq.empty()) {
      int k = qq.front();
      qq.pop();
      for (auto &i : v[k]) {
        if (len == d[i.first] && i.second == pre_nx) {
          if (mn[i.first] < nx) {
            nx = mn[i.first];
            while (!ww.empty()) ww.pop();
            if (!visited[i.first]) ww.push(i.first);
            pp[i.first] = k;
          } else if (mn[i.first] == nx) {
            if (!visited[i.first]) ww.push(i.first);
            pp[i.first] = k;
          }
          visited[i.first] = true;
        }
      }
    }
    while (!ww.empty()) {
      visited[ww.front()] = 0;
      qq.push(ww.front());
      ww.pop();
    }
  }
  vector<int> ans;
  for (int i = 0; i != -1; i = pp[i]) ans.push_back(i);
  if (ans.size() == 1) putchar('0');
  puts("");
  for (int i = ppz[ans[((int)(ans).size()) - 1]]; i != -1; i = ppz[i])
    ans.push_back(i);
  cout << ans.size() << endl;
  for (int i = 0; i < ((int)(ans).size()); ++i)
    printf("%d%c", ans[i], ans[i] != n - 1 ? ' ' : '\n');
}
