#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int> > nei[100007];
int zdist[100007], bfsdist[100007];
int zsyg[100007], bfssyg[100007];
pair<int, int> syg[100007];
set<int> s, ns;
void bfs(int v, int dist[], int syg[], bool zer) {
  bool ok[10] = {};
  ok[0] = 1;
  if (!zer) memset((void*)ok, -1, sizeof(ok));
  for (int i = 0; i < 100007; i++) dist[i] = ((int)0x7f7f7f7f);
  dist[v] = 0;
  queue<int> q;
  q.push(v);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (pair<int, int> u : nei[v]) {
      if (ok[u.second] && dist[v] + 1 < dist[u.first]) {
        dist[u.first] = dist[v] + 1;
        syg[u.first] = v;
        q.push(u.first);
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  while (m--) {
    int a, b, len;
    scanf("%d%d%d", &a, &b, &len);
    nei[a].push_back(make_pair(b, len));
    nei[b].push_back(make_pair(a, len));
  }
  bfs(n - 1, zdist, zsyg, 1);
  bfs(0, bfsdist, bfssyg, 0);
  int rlen = ((int)0x7f7f7f7f);
  for (int i = 0; i < n; i++)
    if (i == n - 1 || zdist[i] < ((int)0x7f7f7f7f))
      if (bfsdist[i] < rlen) rlen = bfsdist[i];
  for (int i = 0; i < 100007; i++) syg[i] = make_pair(((int)0x7f7f7f7f), 0);
  for (int i = 0; i < n; i++)
    if (i == n - 1 || zdist[i] < ((int)0x7f7f7f7f))
      if (bfsdist[i] == rlen) syg[i] = make_pair(zdist[i], i), s.insert(i);
  for (int i = 0; i < rlen; i++) {
    ns.clear();
    int best = 10;
    for (__typeof(s.begin()) it = s.begin(); it != s.end(); it++) {
      for (int j = 0; j < ((int)(nei[*it]).size()); j++) {
        pair<int, int> u = nei[*it][j];
        if (bfsdist[*it] - 1 != bfsdist[u.first]) continue;
        if (u.second < best) {
          best = u.second;
          ns.clear();
        }
        if (u.second == best) {
          if (ns.find(u.first) != ns.end())
            syg[u.first] = min(syg[u.first], make_pair(syg[*it].first, *it));
          else {
            ns.insert(u.first);
            syg[u.first] = make_pair(syg[*it].first, *it);
          }
        }
      }
    }
    printf("%d", best);
    s = ns;
  }
  if (rlen == 0) printf("0");
  printf("\n");
  printf("%d\n", rlen + syg[0].first + 1);
  int x = 0;
  for (int i = 0; i < rlen; i++) {
    printf("%d ", x);
    x = syg[x].second;
  }
  for (int i = 0; i <= syg[0].first; i++) {
    printf("%d ", x);
    x = zsyg[x];
  }
  printf("\n");
  return 0;
}
