#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
template <class T>
inline bool read(T &n) {
  T x = 0, tmp = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
  if (c == EOF) return false;
  if (c == '-') c = getchar(), tmp = -1;
  while (c >= '0' && c <= '9') x *= 10, x += (c - '0'), c = getchar();
  n = x * tmp;
  return true;
}
template <class T>
inline void write(T n) {
  if (n < 0) {
    putchar('-');
    n = -n;
  }
  int len = 0, data[20];
  while (n) {
    data[len++] = n % 10;
    n /= 10;
  }
  if (!len) data[len++] = 0;
  while (len--) putchar(data[len] + 48);
}
const int MAXN = 100010;
int dis[MAXN], dist[MAXN], pre[MAXN];
struct Node {
  int to, cost;
  Node() {}
  Node(int a, int b) : to(a), cost(b) {}
  bool operator<(const Node &o) const { return cost < o.cost; }
};
vector<Node> g[MAXN];
vector<int> ss, ss1;
vector<int> ans;
queue<int> q;
int vis[MAXN];
void bfs(int s) {
  dis[s] = 0;
  q.push(s);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i].to;
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        q.push(v);
      }
    }
  }
}
void findpre(int s) {
  q.push(s);
  dist[s] = 0;
  int minn = dis[s];
  while (q.size()) {
    int u = q.front();
    q.pop();
    if (dis[u] < minn) {
      minn = dis[u];
      ss.clear();
      ss.push_back(u);
    } else if (dis[u] == minn)
      ss.push_back(u);
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i].to;
      if (!g[u][i].cost && dist[v] > dist[u] + 1) {
        dist[v] = dist[u] + 1;
        pre[v] = u;
        q.push(v);
      }
    }
  }
}
void bfs1() {
  int d = dis[ss[0]];
  ans.clear();
  while (d) {
    ss1.clear();
    d--;
    int minn = 10;
    for (int i = 0; i < ss.size(); i++)
      for (int u = ss[i], j = 0; j < g[u].size(); j++)
        if (dis[g[u][j].to] == d) minn = min(minn, g[u][j].cost);
    ans.push_back(minn);
    for (int i = 0; i < ss.size(); i++)
      for (int u = ss[i], j = 0; j < g[u].size(); j++) {
        int v = g[u][j].to;
        if (dis[v] == d && g[u][j].cost == minn && !vis[v])
          vis[v] = 1, ss1.push_back(v), pre[v] = u;
      }
    ss.clear();
    for (int i = 0; i < ss1.size(); i++) ss.push_back(ss1[i]);
  }
}
void findans(int u, int d) {
  int next = u;
  ans.push_back(u);
  while (next != d) {
    next = pre[next];
    ans.push_back(next);
  }
}
int main() {
  memset(dis, 0x3f3f3f3f, sizeof(dis));
  memset(dist, 0x3f3f3f3f, sizeof(dist));
  int n, m;
  read(n), read(m);
  for (int i = 1, u, v, w; i <= m; i++) {
    read(u), read(v), read(w);
    g[u].push_back(Node(v, w));
    g[v].push_back(Node(u, w));
  }
  bfs(0);
  findpre(n - 1);
  bfs1();
  if (ans.size() == 0)
    printf("0");
  else {
    for (int i = 0; i < ans.size(); i++) printf("%d", ans[i]);
  }
  putchar('\n');
  ans.clear();
  findans(0, n - 1);
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
  putchar('\n');
  return 0;
}
