#include <bits/stdc++.h>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("O8")
#pragma GCC optimization("unroll-loops")
using namespace std;
const long long int N = 1e5 + 25, mod = 1e9 + 7, inf = 1e16, maxq = 5e5 + 30,
                    maxm = 1e3 + 30;
const long double eps = 0.0000001;
long long int poww(long long int a, long long int b) {
  return (!b ? 1
             : (b & 1 ? a * poww(a * a % mod, b / 2) % mod
                      : poww(a * a % mod, b / 2) % mod));
}
int n, m, d[N];
pair<int, int> par[N];
bool mark[N], vis[N];
vector<pair<int, int> > adj[N], dag[N];
void dfs() {
  queue<int> q;
  mark[n - 1] = 1;
  vis[n - 1] = 1;
  q.push(n - 1);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (pair<int, int> u : adj[v])
      if (!vis[u.first] && u.second == 0) {
        vis[u.first] = 1;
        mark[u.first] = 1;
        q.push(u.first);
        par[u.first].first = v;
        par[u.first].second = 0;
      }
  }
  return;
}
void bfs() {
  queue<int> q;
  for (int i = 0; i < n; i++) {
    if (mark[i]) {
      d[i] = 0;
      q.push(i);
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (pair<int, int> v : adj[u]) {
      if (d[v.first] == -1) {
        d[v.first] = d[u] + 1;
        q.push(v.first);
      }
    }
  }
  return;
}
void dg(int v) {
  vis[v] = 1;
  for (pair<int, int> u : adj[v]) {
    if (d[u.first] + 1 == d[v]) {
      dag[u.first].push_back({v, u.second});
      if (!vis[u.first]) dg(u.first);
    }
  }
}
void ans() {
  memset(vis, 0, sizeof vis);
  bool f = 0;
  vector<int> ve, ve2;
  for (int i = 0; i < n; i++) {
    if (mark[i]) {
      ve.push_back(i);
      vis[i] = 1;
    }
  }
  for (int i = 1; i < 100000; i++) {
    if (f) break;
    ve2.clear();
    int mi = 30;
    for (int u : ve) {
      vis[u] = 1;
      for (pair<int, int> v : dag[u]) {
        if (v.first == 0) {
          if (par[v.first].second == -1 || par[0].second > v.second) {
            par[0] = {u, v.second};
            f = 1;
          }
        }
        if (vis[v.first]) continue;
        if (v.second < mi) {
          ve2.clear();
          mi = v.second;
          ve2.push_back(v.first);
          if (u == 3)
            cerr << "v.X"
                 << ": " << v.first << '\n';
          ;
          par[v.first] = {u, v.second};
        } else if (v.second == mi) {
          ve2.push_back(v.first);
          par[v.first] = {u, v.second};
        }
      }
      if (!u) f = 1;
    }
    swap(ve2, ve);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  memset(d, -1, sizeof d);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  for (int i = 0; i < n; i++) par[i] = {-1, -1};
  dfs();
  if (mark[0]) {
    cout << 0 << '\n';
    int v = 0;
    vector<int> ve;
    while (v != -1) {
      ve.push_back(v);
      v = par[v].first;
    }
    cout << ve.size() << '\n';
    for (int u : ve) cout << u << ' ';
    return 0;
  }
  bfs();
  memset(vis, 0, sizeof vis);
  dg(0);
  ans();
  int v = 0;
  string s = "";
  vector<int> ve;
  while (v != -1) {
    ve.push_back(v);
    if (par[v].second != -1 && !mark[v]) s = char(par[v].second + int('0')) + s;
    v = par[v].first;
  }
  cout << s << '\n';
  cout << ve.size() << '\n';
  for (int u : ve) cout << u << ' ';
  return 0;
}
