#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int> > nei[100007];
int dis[100007];
int mindis;
vector<int> ans, path;
int after[100007];
int pre[100007];
int lgl[100007];
void dfs(int now) {
  mindis = min(mindis, dis[now]);
  lgl[now] = 1;
  for (pair<int, int> i : nei[now])
    if (!lgl[i.first] && !i.second) dfs(i.first);
}
int main() {
  memset((void*)dis, -1, sizeof(dis));
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    nei[a].push_back(make_pair(b, c));
    nei[b].push_back(make_pair(a, c));
  }
  queue<pair<int, int> > q;
  q.push(make_pair(0, 0));
  dis[0] = 0;
  while (((int)(q).size())) {
    pair<int, int> qq = q.front();
    q.pop();
    for (pair<int, int> i : nei[qq.first])
      if (dis[i.first] == -1) {
        dis[i.first] = qq.second + 1;
        q.push(make_pair(i.first, qq.second + 1));
      }
  }
  mindis = dis[n - 1];
  dfs(n - 1);
  set<int> grp[2];
  int cur = 0, nxt = 1;
  for (int i = 0; i < n; i++)
    if (lgl[i] && dis[i] == mindis) grp[0].insert(i);
  for (int dd = mindis - 1; dd >= 0; dd--) {
    grp[nxt].clear();
    int minlen = 10;
    for (int i : grp[cur])
      for (pair<int, int> j : nei[i])
        if (dis[j.first] == dd) minlen = min(minlen, j.second);
    for (int i : grp[cur])
      for (pair<int, int> j : nei[i])
        if (dis[j.first] == dd && j.second == minlen) grp[nxt].insert(j.first);
    ans.push_back(minlen);
    swap(cur, nxt);
  }
  for (int i : ans) cout << i;
  if (!((int)(ans).size())) cout << 0;
  cout << endl;
  reverse((ans).begin(), (ans).end());
  grp[cur].clear();
  grp[cur].insert(0);
  lgl[0] = 0;
  memset((void*)pre, -1, sizeof(pre));
  for (int dd = 1; dd <= mindis; dd++) {
    grp[nxt].clear();
    for (int i : grp[cur])
      for (pair<int, int> j : nei[i])
        if (dis[j.first] == dd && j.second == ans[dd - 1]) {
          grp[nxt].insert(j.first);
          pre[j.first] = i;
          lgl[j.first] = -dd;
        }
    swap(cur, nxt);
  }
  queue<int> q2;
  memset((void*)after, -1, sizeof(after));
  q2.push(n - 1);
  after[n - 1] = -2;
  int m1 = -1;
  while (1) {
    int qq = q2.front();
    q2.pop();
    if (lgl[qq] == -mindis) {
      m1 = qq;
      break;
    }
    for (pair<int, int> i : nei[qq])
      if (i.second == 0 && after[i.first] == -1) {
        after[i.first] = qq;
        q2.push(i.first);
      }
  }
  int m2 = m1;
  while (m2 >= 0) {
    path.push_back(m2);
    m2 = pre[m2];
  }
  reverse((path).begin(), (path).end());
  m1 = after[m1];
  while (m1 >= 0) {
    path.push_back(m1);
    m1 = after[m1];
  }
  cout << ((int)(path).size()) << endl;
  cout << path[0];
  for (int i = 1; i < ((int)(path).size()); i++) cout << ' ' << path[i];
  cout << endl;
  return 0;
}
