#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[100011];
vector<int> cost, ans, g[10][100011];
int dist[100011];
int revdist[100011], vis[100011], par[100011];
vector<pair<int, int> > comp[2];
int dfs(int u, int d, int c) {
  if (u == 0) {
    ans.push_back(0);
    return 1;
  }
  vis[u] = 1;
  for (int i = 0; i < adj[u].size(); i++) {
    int k = adj[u][i].second;
    if (vis[k] || cost[c] != adj[u][i].first || dist[k] != d) continue;
    if (dfs(k, d - 1, c + 1)) {
      ans.push_back(u);
      return 1;
    }
  }
  return 0;
}
int main() {
  int i, j, n, m;
  scanf("%d %d", &n, &m);
  for (i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    adj[u].push_back(make_pair(w, v));
    adj[v].push_back(make_pair(w, u));
    g[w][u].push_back(v);
    g[w][v].push_back(u);
  }
  queue<int> q;
  for (i = 0; i < n; i++) dist[i] = 1000000000;
  for (i = 0; i < n; i++) revdist[i] = 1000000000;
  dist[0] = 0;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < adj[u].size(); i++) {
      int k = adj[u][i].second;
      if (dist[u] + 1 < dist[k]) {
        dist[k] = dist[u] + 1;
        q.push(k);
      }
    }
  }
  revdist[n - 1] = 0;
  q.push(n - 1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < adj[u].size(); i++) {
      int k = adj[u][i].second;
      if (adj[u][i].first != 0) continue;
      if (revdist[u] + 1 < revdist[k]) {
        par[k] = u;
        revdist[k] = revdist[u] + 1;
        q.push(k);
      }
    }
  }
  int d = 1000000000;
  for (i = 0; i < n; i++)
    if (revdist[i] != 1000000000) d = min(d, dist[i]);
  int c = 0;
  for (i = 0; i < n; i++)
    if (dist[i] == d && revdist[i] != 1000000000)
      comp[0].push_back(make_pair(i, i));
  while (d > 0) {
    d--;
    comp[!c].clear();
    for (i = 0; i < 10; i++) {
      int flag = 0;
      for (j = 0; j < comp[c].size(); j++) {
        int k = comp[c][j].first;
        for (int l = 0; l < g[i][k].size(); l++) {
          if (dist[g[i][k][l]] == d)
            comp[!c].push_back(make_pair(g[i][k][l], comp[c][j].second));
        }
        if (comp[!c].size() > 0) flag = 1;
      }
      if (flag == 1) {
        cost.push_back(i);
        break;
      }
    }
    c = !c;
  }
  d = 1000000000;
  int loc = -1;
  for (i = 0; i < comp[c].size(); i++) {
    if (revdist[comp[c][i].second] < d) {
      d = revdist[comp[c][i].second];
      loc = comp[c][i].second;
    }
  }
  assert(loc != -1);
  dfs(loc, dist[loc] - 1, 0);
  ans.erase(ans.end() - 1);
  for (i = loc; i != n - 1; i = par[i]) ans.push_back(i);
  ans.push_back(n - 1);
  if (cost.size() == 0) printf("0");
  for (i = 0; i < cost.size(); i++) printf("%d", cost[i]);
  cout << endl;
  printf("%d\n", ans.size());
  for (i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
  return 0;
}
