#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 - '0' + c, c = getchar();
  x *= f;
}
const int N = 1e5 + 10;
int n, m, dep[N], S, T;
struct ed {
  int to, w;
};
vector<ed> G[N];
void ad(int x, int y, int w) {
  G[x].push_back((ed){y, w}), G[y].push_back((ed){x, w});
}
int que[N], hd, tl;
int pre[N], d1[N];
queue<int> orz;
void dfs1() {
  que[++tl] = T, dep[T] = 1, orz.push(T);
  while (!orz.empty()) {
    int u = orz.front();
    orz.pop();
    for (int i = 0; i < G[u].size(); ++i)
      if (G[u][i].w == 0) {
        int v = G[u][i].to;
        if (!dep[v]) pre[v] = u, dep[v] = 1, orz.push(v), que[++tl] = v;
      }
  }
}
queue<int> q;
void bfs1() {
  q.push(S);
  d1[S] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (dep[u]) continue;
    for (int i = 0; i < G[u].size(); ++i) {
      int v = G[u][i].to;
      if (!d1[v]) d1[v] = d1[u] + 1, q.push(v);
    }
  }
}
vector<int> Ansa;
void bfs() {
  hd = 1;
  dfs1();
  if (dep[S]) printf("0");
  bfs1();
  while (hd <= tl) {
    if (dep[S]) break;
    int mx = 10, d = dep[que[hd]], midp = n + 233;
    for (int i = hd; i <= tl && dep[que[i]] == d; ++i) {
      int u = que[i];
      for (int k = 0; k < G[u].size(); ++k) {
        int v = G[u][k].to;
        if (d1[u] == d1[v] + 1 && !dep[v]) {
          if (midp > d1[v])
            midp = d1[v], mx = G[u][k].w;
          else if (midp == d1[v])
            mx = min(G[u][k].w, mx);
        }
      }
    }
    printf("%d", mx);
    while (hd <= tl && dep[que[hd]] == d) {
      int u = que[hd++];
      for (int k = 0; k < G[u].size(); ++k)
        if (G[u][k].w == mx) {
          int v = G[u][k].to;
          if (d1[u] == d1[v] + 1 && !dep[v] && d1[v] == midp)
            dep[v] = dep[u] + 1, pre[v] = u, que[++tl] = v;
        }
    }
  }
  for (int i = S; i; i = pre[i]) Ansa.push_back(i - 1);
  printf("\n%d\n", Ansa.size());
  for (int i = 0; i < Ansa.size(); ++i) printf("%d ", Ansa[i]);
}
int main() {
  int x, y, w;
  read(n), read(m);
  for (int i = 1; i <= m; ++i) read(x), read(y), read(w), x++, y++, ad(x, y, w);
  S = 1, T = n;
  bfs();
  return 0;
}
