#include <bits/stdc++.h>
using namespace std;
const int tamN = 100005;
vector<pair<int, int> > g[tamN];
int d[tamN], dzeros[tamN];
bool was[tamN];
int pr[tamN], level[tamN], spr[tamN];
int main() {
  int m, n, x, y, c;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int from, to, price;
    scanf("%d %d %d", &from, &to, &price);
    g[from].push_back({to, price});
    g[to].push_back({from, price});
  }
  for (int i = 0; i < n; ++i) {
    d[i] = -1;
  }
  d[0] = 0;
  queue<int> Q;
  Q.push(0);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (auto next : g[u]) {
      if (d[next.first] == -1) {
        d[next.first] = 1 + d[u];
        Q.push(next.first);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    dzeros[i] = -1;
  }
  dzeros[n - 1] = 0;
  Q.push(n - 1);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (auto next : g[u]) {
      if (dzeros[next.first] == -1 && next.second == 0) {
        dzeros[next.first] = 1 + dzeros[u];
        pr[next.first] = u;
        Q.push(next.first);
      }
    }
  }
  int len = n;
  for (int i = 0; i < n; ++i) {
    if (dzeros[i] != -1 && d[i] < len) {
      len = d[i];
    }
  }
  for (int i = 0; i < n; ++i) {
    level[i] = -1;
    was[i] = false;
  }
  level[0] = 0;
  queue<pair<int, pair<int, int> > > general;
  for (int i = 0; i < n; ++i) {
    if (dzeros[i] != -1 && d[i] == len) {
      general.push({i, {0, 0}});
    }
  }
  while (!general.empty()) {
    auto tmp = general.front();
    general.pop();
    int u = tmp.first;
    int peso = tmp.second.first;
    int where = tmp.second.second;
    if (peso == level[where] && !was[u]) {
      was[u] = true;
      for (auto next : g[u]) {
        if (d[next.first] + 1 + where == len) {
          if (level[where + 1] == -1 || next.second < level[where + 1]) {
            level[where + 1] = next.second;
          }
          general.push({next.first, {next.second, where + 1}});
        }
      }
    }
  }
  for (int i = 1; i <= len; ++i) {
    cout << level[i];
  }
  if (!len) {
    cout << 0;
  }
  cout << endl;
  for (int i = 0; i < n; ++i) {
    was[i] = false;
  }
  queue<pair<int, int> > last;
  last.push({0, 0});
  was[0] = true;
  while (!last.empty()) {
    auto tmp = last.front();
    last.pop();
    int u = tmp.first;
    int where = tmp.second;
    if (where >= len) {
      continue;
    }
    for (auto next : g[u]) {
      if (next.second == level[len - where] && !was[next.first]) {
        was[next.first] = true;
        last.push({next.first, where + 1});
        spr[next.first] = u;
      }
    }
  }
  int idx = -1;
  for (int i = 0; i < n; ++i) {
    if (dzeros[i] != -1 && d[i] == len && was[i]) {
      if (idx == -1 || dzeros[i] < dzeros[idx]) {
        idx = i;
      }
    }
  }
  cout << len + dzeros[idx] + 1 << endl;
  deque<int> solve;
  int current = idx;
  while (current != n - 1) {
    solve.push_back(current);
    current = pr[current];
  }
  solve.push_back(n - 1);
  if (idx != 0) {
    current = idx;
    while (current != 0) {
      if (current != idx) {
        solve.push_front(current);
      }
      current = spr[current];
    }
    solve.push_front(0);
  }
  while (!solve.empty()) {
    cout << solve.front() << " ";
    solve.pop_front();
  }
  return 0;
}
