#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[102400];
pair<int, int> fa[102400];
int fpar[102400], fdist[102400], bpar[102400], bdist[102400];
void bfs(int u, int par[], int dist[], bool zero) {
  bool accept[10] = {};
  memset(accept, false, sizeof(accept));
  accept[0] = true;
  if (!zero) {
    for (int i = 0; i < 10; i++) accept[i] = true;
  }
  for (int i = 0; i < 102400; i++) dist[i] = 0x3FFFFFFF;
  dist[u] = 0;
  queue<int> que;
  que.push(u);
  while (!que.empty()) {
    int x = que.front();
    que.pop();
    for (int i = 0; i < adj[x].size(); i++) {
      int v = adj[x][i].first, d = adj[x][i].second;
      if (accept[d] && dist[v] > dist[x] + 1) {
        par[v] = x;
        dist[v] = dist[x] + 1;
        que.push(v);
      }
    }
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
  }
  bfs(n - 1, bpar, bdist, true);
  bfs(0, fpar, fdist, false);
  int len = 0x3FFFFFFF;
  for (int i = 0; i < n; i++) {
    if (i == n - 1 || bdist[i] < 0x3FFFFFFF) len = min(len, fdist[i]);
  }
  set<int> s;
  for (int i = 0; i < n; i++) {
    fa[i] = make_pair(0x3FFFFFFF, 0);
    if ((i == n - 1 || bdist[i] < 0x3FFFFFFF) && fdist[i] == len) {
      s.insert(i);
      fa[i] = make_pair(bdist[i], i);
    }
  }
  for (int i = 0; i < len; i++) {
    set<int> news;
    int mn = 1024;
    for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
      for (int j = 0; j < adj[*it].size(); j++) {
        if (fdist[*it] != fdist[adj[*it][j].first] + 1) continue;
        if (adj[*it][j].second < mn) {
          mn = adj[*it][j].second;
          news.clear();
        }
        if (mn == adj[*it][j].second) {
          if (news.find(adj[*it][j].first) != news.end())
            fa[adj[*it][j].first] =
                min(fa[adj[*it][j].first], make_pair(fa[*it].first, *it));
          else {
            news.insert(adj[*it][j].first);
            fa[adj[*it][j].first] = make_pair(fa[*it].first, *it);
          }
        }
      }
    }
    printf("%d", mn);
    s = news;
  }
  if (!len) printf("0");
  printf("\n");
  printf("%d\n", len + fa[0].first + 1);
  int u = 0;
  for (int i = 0; i < len; i++) {
    printf("%d ", u);
    u = fa[u].second;
  }
  for (int i = 0; i < fa[0].first; i++) {
    printf("%d ", u);
    u = bpar[u];
  }
  printf("%d\n", u);
  return 0;
}
