#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 100 + 10;
int n, m, d[N], mn[N], par[N], par_kooft[N], zahr[N];
bool vis[N], mark[N];
vector<pair<int, int>> adj[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 0, v, u, w; i < m; i++) {
    cin >> v >> u >> w;
    adj[v].push_back({u, w});
    adj[u].push_back({v, w});
  }
  queue<int> q;
  fill(d, d + n, 1 << 30);
  q.push(0), d[0] = 0;
  while (q.size()) {
    int v = q.front();
    q.pop();
    for (auto u : adj[v])
      if (d[v] + 1 < d[u.first]) {
        d[u.first] = d[v] + 1;
        q.push(u.first);
      }
  }
  q.push(n - 1), vis[n - 1] = true;
  fill(zahr, zahr + n, 1 << 30);
  zahr[n - 1] = 0;
  while (q.size()) {
    int v = q.front();
    q.pop();
    for (auto u : adj[v])
      if (u.second == 0 && !vis[u.first]) {
        vis[u.first] = true;
        zahr[u.first] = zahr[v] + 1;
        par_kooft[u.first] = v;
        q.push(u.first);
      }
  }
  int dis = 1 << 30;
  for (int i = 0; i < n; i++)
    if (vis[i]) dis = min(dis, d[i]);
  mn[0] = 10;
  for (int i = 1; i < n; i++) {
    mn[i] = 10;
    if (!vis[i]) {
      for (auto u : adj[i])
        if (u.second < mn[i] && d[u.first] == d[i] - 1) mn[i] = u.second;
    } else {
      for (auto u : adj[i])
        if (u.second && u.second < mn[i] && d[u.first] == d[i] - 1)
          mn[i] = u.second;
    }
  }
  vector<int> vec;
  for (int i = 0; i < n; i++)
    if (vis[i] && d[i] == dis) vec.push_back(i), mark[i] = true;
  sort(vec.begin(), vec.end(), [](int v, int u) { return zahr[v] < zahr[u]; });
  string len;
  fill(par, par + N, -1);
  while (vec.size()) {
    int best = 10;
    for (auto x : vec) best = min(mn[x], best);
    if (best == 10) break;
    len += (char)(best + '0');
    vector<int> nxts;
    for (auto v : vec)
      for (auto u : adj[v])
        if (u.second == best && !mark[u.first] && d[u.first] == d[v] - 1) {
          nxts.push_back(u.first), mark[u.first] = true;
          par[u.first] = v;
        }
    vec.clear();
    for (auto x : nxts) vec.push_back(x);
  }
  if (len == "") len = "0";
  cout << len << '\n';
  vector<int> ans;
  int s = 0;
  while (!vis[s]) {
    ans.push_back(s);
    s = par[s];
  }
  while (s != n - 1) {
    ans.push_back(s);
    s = par_kooft[s];
  }
  ans.push_back(s);
  cout << (int)(ans.size()) << '\n';
  for (auto v : ans) cout << v << ' ';
  cout << '\n';
  return 0;
}
