#include <bits/stdc++.h>
int MOD = int(1e9) + 7;
const int INF = MOD;
inline int add(int a, int b) {
  return (a + b >= MOD) ? (a + b - MOD) : (a + b);
}
inline void inc(int &a, int b) { a = add(a, b); }
inline int sub(int a, int b) { return (a - b < 0) ? (a - b + MOD) : (a - b); }
inline void dec(int &a, int b) { a = sub(a, b); }
inline int mul(int a, int b) { return (a * 1ll * b) % MOD; }
using namespace std;
const int N = 100000;
vector<pair<int, int> > ladj[N];
queue<int> Q;
int pos[N], W[N], zeroes[N], dist[N], n;
vector<int> can[N][10], layer, aux, vertices;
string ans;
void bfs(int n) {
  Q.push(n - 1);
  zeroes[n - 1] = 0;
  pos[n - 1] = -1;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (auto i : ladj[u]) {
      int v = i.first, w = i.second;
      if (zeroes[v] > -1 or w) continue;
      pos[v] = u;
      zeroes[v] = zeroes[u] + 1;
      Q.push(v);
    }
  }
}
void bfs2(int n) {
  Q.push(0);
  dist[0] = 0;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = 0; i < (int(ladj[u].size())); i++) {
      int v = ladj[u][i].first, w = ladj[u][i].second;
      if (dist[v] < dist[u] + 1) continue;
      if (dist[v] > dist[u] + 1) {
        for (int j = 0; j < 10; j++) can[v][j].clear();
        dist[v] = dist[u] + 1;
        Q.push(v);
      }
      can[v][w].push_back(u);
    }
  }
}
void solve(int n) {
  int mini = INT_MAX;
  for (int i = 0; i < n; i++)
    if (zeroes[i] > -1) mini = min(mini, dist[i]);
  for (int i = 0; i < n; i++)
    if (zeroes[i] > -1 and dist[i] == mini) layer.push_back(i);
  while (true) {
    for (int i : layer)
      if (!i) return;
    for (int j = 0; j < 10; j++) {
      bool flag = false;
      for (int i : layer)
        if (!can[i][j].empty()) flag = true;
      if (flag) {
        mini = j;
        break;
      }
    }
    aux.clear();
    for (int i : layer)
      for (int j : can[i][mini])
        if (pos[j] == -1 or zeroes[j] > zeroes[i]) {
          pos[j] = i;
          zeroes[j] = zeroes[i];
          aux.push_back(j);
          W[j] = mini;
        }
    sort((aux).begin(), (aux).end());
    aux.erase(unique((aux).begin(), (aux).end()), aux.end());
    layer = aux;
  }
}
void get(int u) {
  vertices.push_back(u);
  if (pos[u] == -1) return;
  ans.push_back((char)(W[u] + '0'));
  get(pos[u]);
}
int main() {
  int m;
  scanf("%d %d", &n, &m);
  fill(pos, pos + n, -1);
  fill(zeroes, zeroes + n, -1);
  fill(dist, dist + n, INF);
  while (m--) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    ladj[u].push_back({v, w});
    ladj[v].push_back({u, w});
  }
  bfs(n);
  bfs2(n);
  solve(n);
  get(0);
  while ((int(ans.size())) > 1 and ans.back() == '0') ans.pop_back();
  reverse((ans).begin(), (ans).end());
  printf("%s\n%d\n", ans.c_str(), (int(vertices.size())));
  for (int i : vertices) printf("%d ", i);
  return 0;
}
