#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int read() {
  int f = 1, x = 0;
  char c = getchar();
  while (c < '0' || '9' < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return f * x;
}
vector<int> G[200000 + 5][10];
void Addedge(int u, int v, int w) {
  G[u][w].push_back(v);
  G[v][w].push_back(u);
  return;
}
int dis[200000 + 5];
bool vis[200000 + 5];
int q[2][200000 + 5], tp[2];
int pre[200000 + 5], prw[200000 + 5];
void BFS1(int S) {
  queue<int> Q;
  Q.push(S), vis[S] = 1;
  while (!Q.empty()) {
    int u = Q.front();
    q[0][++tp[0]] = u;
    Q.pop();
    for (int i = 0; i < (int)G[u][0].size(); i++) {
      int v = G[u][0][i];
      if (!vis[v]) pre[v] = u, prw[v] = 0, vis[v] = 1, Q.push(v);
    }
  }
  return;
}
void BFS2(int S) {
  queue<int> Q;
  Q.push(S), dis[S] = 1;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int t = 0; t <= 9; t++) {
      for (int i = 0; i < (int)G[u][t].size(); i++) {
        int v = G[u][t][i];
        if (!dis[v]) dis[v] = dis[u] + 1, Q.push(v);
      }
    }
  }
  return;
}
void BFS3() {
  int s = 0;
  while (1) {
    tp[s ^ 1] = 0;
    if (!tp[s]) break;
    int md = 0x3f3f3f3f, mt = 0x3f3f3f3f;
    for (int i = 1; i <= tp[s]; i++) {
      int u = q[s][i];
      for (int t = 0; t <= 9; t++)
        for (int j = 0; j < (int)G[u][t].size(); j++) {
          int v = G[u][t][j];
          if (md > dis[v])
            md = dis[v], mt = t;
          else if (md == dis[v])
            mt = min(mt, t);
        }
    }
    for (int i = 1; i <= tp[s]; i++) {
      int u = q[s][i];
      for (int j = 0; j < (int)G[u][mt].size(); j++) {
        int v = G[u][mt][j];
        if (!vis[v] && dis[v] == md)
          pre[v] = u, prw[v] = mt, vis[v] = 1, q[s ^ 1][++tp[s ^ 1]] = v;
      }
    }
    s ^= 1;
  }
  return;
}
int ans1[200000 + 5], len1, ans2[200000 + 5], len2;
int main() {
  int n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    int u = read() + 1, v = read() + 1, w = read();
    Addedge(u, v, w);
  }
  BFS1(n);
  BFS2(1);
  BFS3();
  int u = 1;
  ans2[++len2] = u;
  while (u != n) {
    ans1[++len1] = prw[u];
    u = pre[u];
    ans2[++len2] = u;
  }
  int t = 0;
  for (int i = len1; i >= 1; i--)
    if (ans1[i] || t) t = 1, printf("%d", ans1[i]);
  if (!t) putchar('0');
  puts("");
  printf("%d\n", len2);
  for (int i = 1; i <= len2; i++)
    printf("%d", ans2[i] - 1), putchar(i == len2 ? '\n' : ' ');
  return 0;
}
