#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e9 + 19;
int n, m;
vector<pair<int, int> > e[N];
int fin[N];
int dist[N];
int par[N];
int dist0[N];
int how[N];
void read() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int v, u, cost;
    scanf("%d%d%d", &v, &u, &cost);
    e[v].push_back(make_pair(u, cost));
    e[u].push_back(make_pair(v, cost));
  }
}
void bfs0() {
  queue<int> q;
  memset(dist0, 63, sizeof(dist0));
  q.push(n - 1);
  dist0[n - 1] = 0;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    fin[v] = 1;
    for (auto x : e[v]) {
      if (x.second == 0 && dist0[x.first] > dist0[v]) {
        dist0[x.first] = dist0[v] + 1;
        par[x.first] = v;
        q.push(x.first);
      }
    }
  }
}
void bfs1() {
  queue<int> q;
  memset(dist, 63, sizeof(dist));
  q.push(0);
  dist[0] = 0;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    if (fin[v]) continue;
    for (auto x : e[v])
      if (dist[x.first] > dist[v] + 1) {
        dist[x.first] = dist[v] + 1;
        q.push(x.first);
      }
  }
}
void solve() {
  bfs0();
  bfs1();
  int mnDist = INF;
  for (int i = 0; i < n; i++)
    if (fin[i]) {
      mnDist = min(mnDist, dist[i]);
    }
  assert(mnDist < INF);
  vector<int> who;
  for (int i = 0; i < n; i++)
    if (fin[i]) who.push_back(i);
  for (int target = mnDist - 1; target >= 0; target--) {
    int low = 10;
    assert(!who.empty());
    for (auto v : who) {
      for (auto x : e[v]) {
        if (dist[x.first] == target) {
          low = min(low, x.second);
        }
      }
    }
    assert(low < 10);
    vector<int> tmp;
    for (auto v : who)
      for (auto x : e[v])
        if (dist[x.first] == target && low == x.second) {
          if (dist0[x.first] > INF) tmp.push_back(x.first);
          if (dist0[x.first] > dist0[v]) {
            dist0[x.first] = dist0[v];
            par[x.first] = v;
            how[x.first] = x.second;
          }
        }
    who = tmp;
  }
  vector<int> number;
  vector<int> path;
  int v = 0;
  for (; v != n - 1; v = par[v]) {
    number.push_back(how[v]);
    path.push_back(v);
  }
  path.push_back(n - 1);
  reverse((number).begin(), (number).end());
  int cur = 0;
  for (; cur < (int)number.size() && number[cur] == 0; cur++)
    ;
  if (cur == (int)number.size())
    puts("0");
  else {
    for (int i = cur; i < (int)number.size(); i++) printf("%d", number[i]);
    printf("\n");
  }
  printf("%d\n", (int)path.size());
  for (auto x : path) printf("%d ", x);
  printf("\n");
}
void printAns() {}
void stress() {}
int main() {
  if (1) {
    int k = 1;
    for (int tt = 0; tt < k; tt++) {
      read();
      solve();
      printAns();
    }
  } else {
    stress();
  }
  return 0;
}
