#include <bits/stdc++.h>
using namespace std;
const int Inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
int n, m;
vector<pair<int, int> > nei[1 << 17];
int dis[1 << 17], fa[1 << 17];
int sid[1 << 17], af[1 << 17];
pair<int, int> pre[1 << 17];
void inline bfs(int now, int dis[1 << 17], int fa[1 << 17], int mode) {
  memset(dis, Inf, sizeof(int) * (1 << 17));
  dis[now] = 0;
  queue<int> q;
  q.push(now);
  while (((int)(q).size())) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < (((int)(nei[x]).size())); ++i) {
      int to = nei[x][i].first;
      if (nei[x][i].second && mode) continue;
      if (dis[to] > dis[x] + 1) {
        dis[to] = dis[x] + 1;
        fa[to] = x;
        q.push(to);
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= (m); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    nei[a].push_back(make_pair(b, c));
    nei[b].push_back(make_pair(a, c));
  }
  bfs(0, dis, fa, 0);
  bfs(n - 1, sid, af, 1);
  for (int i = 0; i < (n); ++i) pre[i] = make_pair(Inf, Inf);
  int wei = Inf;
  for (int i = 0; i < (n); ++i)
    if (sid[i] != Inf) {
      wei = min(wei, dis[i]);
    }
  set<int> c;
  for (int i = 0; i < (n); ++i)
    if (sid[i] != Inf && dis[i] == wei) {
      c.insert(i);
      pre[i] = make_pair(sid[i], i);
    }
  for (int i = 0; i < (wei); ++i) {
    set<int> nc;
    int mn = 10;
    for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it) {
      int i = *it;
      for (int j = 0; j < (((int)(nei[i]).size())); ++j) {
        int to = nei[i][j].first;
        if (dis[to] != dis[i] - 1) continue;
        if (nei[i][j].second < mn) {
          mn = nei[i][j].second;
          nc.clear();
        }
        if (nei[i][j].second == mn) {
          if (nc.count(to)) {
            pre[to] = min(pre[to], make_pair(pre[i].first, i));
          } else {
            nc.insert(to);
            pre[to] = make_pair(pre[i].first, i);
          }
        }
      }
    }
    printf("%d", mn);
    c = nc;
  }
  if (!wei) printf("0");
  puts("");
  printf("%d\n", wei + pre[0].first + 1);
  int now = 0;
  for (int i = 0; i < (wei); ++i) {
    printf("%d ", now);
    now = pre[now].second;
  }
  for (int i = 0; i < (pre[0].first + 1); ++i) {
    printf("%d ", now);
    now = af[now];
  }
  puts("");
  return 0;
}
