#include <bits/stdc++.h>
namespace lc {
template <class WeightType>
struct EdgeWithWeight {
  int to;
  WeightType weight;
  EdgeWithWeight(int to, const WeightType &weight) : to(to), weight(weight) {}
};
}  // namespace lc
namespace lc {
template <typename EdgeType>
class AdjacencyList {
 public:
 private:
  std::vector<std::vector<EdgeType> > m_lists;

 public:
  explicit AdjacencyList(int n = 0) : m_lists(n) {}
  template <typename... Args>
  void add_edge(int u, Args &&...args) {
    m_lists[u].emplace_back(args...);
  }
  std::vector<EdgeType> &operator[](int u) { return m_lists[u]; }
};
}  // namespace lc
using namespace std;
static const int INF = 1000000000;
int main() {
  ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  lc::AdjacencyList<lc::EdgeWithWeight<int> > graph(n);
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    graph.add_edge(a, b, c);
    graph.add_edge(b, a, c);
  }
  vector<int> prev(n, -1);
  vector<int> rcount(n, INF);
  queue<int> q;
  q.push(n - 1);
  rcount[n - 1] = 0;
  prev[n - 1] = n - 1;
  while (!q.empty()) {
    const int u = q.front();
    q.pop();
    for (const auto &e : graph[u]) {
      const int v = e.to;
      if (e.weight != 0) {
        continue;
      }
      if (prev[v] < 0) {
        q.push(v);
        prev[v] = u;
        rcount[v] = rcount[u] + 1;
      }
    }
  }
  vector<int> goal_set;
  for (int i = 0; i < n; ++i) {
    if (prev[i] >= 0) {
      goal_set.push_back(i);
    }
  }
  vector<int> dtable(n, INF);
  q.push(0);
  dtable[0] = 0;
  while (!q.empty()) {
    const int u = q.front();
    q.pop();
    for (const auto &e : graph[u]) {
      const int v = e.to;
      if (dtable[v] >= INF) {
        dtable[v] = dtable[u] + 1;
        q.push(v);
      }
    }
  }
  int goal_dist = INF;
  for (int v : goal_set) {
    goal_dist = min(goal_dist, dtable[v]);
  }
  vector<pair<int, int> > cur_set;
  for (int i = 0; i < n; ++i) {
    if (prev[i] >= 0 && dtable[i] == goal_dist) {
      cur_set.emplace_back(i, rcount[i]);
    }
  }
  while (cur_set[0].first != 0) {
    vector<int> next_set;
    int min_digit = 10;
    for (const auto &p : cur_set) {
      const int u = p.first;
      for (const auto &e : graph[u]) {
        const int v = e.to;
        if (dtable[v] >= dtable[u]) {
          continue;
        }
        min_digit = min(min_digit, e.weight);
      }
    }
    for (const auto &p : cur_set) {
      const int u = p.first;
      for (const auto &e : graph[u]) {
        const int v = e.to;
        if (dtable[v] >= dtable[u]) {
          continue;
        }
        if (e.weight == min_digit) {
          rcount[v] = min(rcount[v], rcount[u] + 1);
          next_set.push_back(v);
        }
      }
    }
    for (const auto &p : cur_set) {
      const int u = p.first;
      for (const auto &e : graph[u]) {
        const int v = e.to;
        if (dtable[v] >= dtable[u]) {
          continue;
        }
        if (e.weight == min_digit && rcount[v] == rcount[u] + 1) {
          prev[v] = u;
        }
      }
    }
    sort(next_set.begin(), next_set.end());
    next_set.erase(unique(next_set.begin(), next_set.end()), next_set.end());
    cur_set.clear();
    for (int v : next_set) {
      cur_set.emplace_back(v, rcount[v]);
    }
  }
  vector<int> route, result;
  for (int v = 0; v != n - 1; v = prev[v]) {
    for (const auto &e : graph[v]) {
      if (e.to == prev[v]) {
        result.push_back(e.weight);
        break;
      }
    }
    route.push_back(v);
  }
  while (result.size() > 1 && result.back() == 0) {
    result.pop_back();
  }
  reverse(result.begin(), result.end());
  for (int d : result) {
    cout << d;
  }
  cout << endl;
  route.push_back(n - 1);
  cout << route.size() << endl;
  for (int i = 0; i < static_cast<int>(route.size()); ++i) {
    if (i != 0) {
      cout << " ";
    }
    cout << route[i];
  }
  cout << endl;
  return 0;
}
