#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
const int N = 101000;
int n, m, u, v, w, vis[N], dis[N], valw[N], nxtr[N], dis2[N];
vector<int> pth, r[N];
vector<pair<int, int> > e[N];
pair<int, int> nxt[N], val[N];
queue<int> q;
void dfs(int u) {
  for (auto p : e[u])
    if (p.second == 0) {
      int v = p.first;
      if (make_pair(dis[u], valw[u]) < make_pair(dis[v], valw[v])) {
        dis[v] = dis[u];
        valw[v] = valw[u];
        nxt[v] = make_pair(0, u);
      }
    }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    e[u].push_back(make_pair(v, w));
    e[v].push_back(make_pair(u, w));
    if (w == 0) r[v].push_back(u), r[u].push_back(v);
  }
  vis[0] = 0;
  q.push(0);
  for (int dist = 0; dist < n + 1; dist++) {
    vector<int> cand;
    while (!q.empty() && dis[q.front()] == dist) {
      int u = q.front();
      q.pop();
      for (auto p : e[u]) {
        int v = p.first, w = p.second;
        if (!vis[v]) {
          vis[v] = 1;
          dis[v] = dis[u] + 1;
          q.push(v);
          nxt[v] = make_pair(w, u);
          val[v] = make_pair(w, valw[u]);
          cand.push_back(v);
        }
        if (dis[v] == dis[u] + 1) {
          if (make_pair(w, valw[u]) < val[v]) {
            val[v] = make_pair(w, valw[u]);
            nxt[v] = make_pair(w, u);
          }
        }
      }
    }
    vector<pair<int, int> > cret;
    for (auto p : cand) cret.push_back(val[p]);
    sort((cret).begin(), (cret).end());
    cret.erase(unique((cret).begin(), (cret).end()), cret.end());
    for (auto p : cand)
      valw[p] =
          lower_bound((cret).begin(), (cret).end(), val[p]) - cret.begin();
  }
  for (int i = 0; i < n; i++) vis[i] = 0;
  vis[n - 1] = 1;
  q.push(n - 1);
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (auto v : r[u])
      if (!vis[v]) {
        vis[v] = 1;
        q.push(v);
        nxtr[v] = u;
        dis2[v] = dis2[u] + 1;
      }
  }
  auto mv = make_pair(make_pair(dis[n - 1], valw[n - 1]), make_pair(0, n - 1));
  for (int i = 0; i < n; i++)
    if (vis[i]) {
      mv =
          min(mv, make_pair(make_pair(dis[i], valw[i]), make_pair(dis2[i], i)));
    }
  u = mv.second.second;
  bool led = 1;
  while (u != 0) {
    pth.push_back(u);
    led &= nxt[u].first == 0;
    if (!led) putchar(nxt[u].first + '0');
    u = nxt[u].second;
  }
  if (led) putchar('0');
  puts("");
  reverse((pth).begin(), (pth).end());
  u = mv.second.second;
  while (u != n - 1) {
    u = nxtr[u];
    pth.push_back(u);
  }
  printf("%d\n", ((int)(pth).size()) + 1);
  putchar('0');
  for (auto p : pth) printf(" %d", p);
  puts("");
}
