#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
inline long long input() {
  long long n;
  cin >> n;
  return n;
}
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const long long INF = 8e18;
long long pw(long long a, long long b) {
  return (!b ? 1
             : (b & 1 ? (a * pw(a * a % MOD, b / 2)) % MOD
                      : pw(a * a % MOD, b / 2)));
}
vector<pair<int, int>> g[MAXN];
vector<int> ans, Ans;
int mark[MAXN], dis[MAXN];
int par[MAXN], LAST[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  deque<vector<int>> q;
  deque<int> Q;
  vector<int> V;
  Q.push_back(n - 1);
  V.push_back(n - 1);
  LAST[n - 1] = 0;
  mark[n - 1] = 1;
  par[n - 1] = -1;
  while (!Q.empty()) {
    int cu = Q.front();
    Q.pop_front();
    for (auto y : g[cu]) {
      if (mark[y.first] == 0 && y.second == 0) {
        mark[y.first] = 1;
        Q.push_back(y.first);
        V.push_back(y.first);
        par[y.first] = cu;
        LAST[y.first] = 0;
      }
    }
  }
  q.push_back(V);
  while (!q.empty()) {
    vector<int> v = q.front();
    vector<pair<int, int>> N[10];
    q.pop_front();
    for (auto cu : v) {
      for (auto x : g[cu]) {
        if (!mark[x.first]) {
          N[x.second].push_back({x.first, cu});
        }
      }
    }
    for (int i = 0; i < 10; i++) {
      vector<int> NEW;
      for (auto x : N[i]) {
        if (!mark[x.first]) {
          mark[x.first] = 1;
          par[x.first] = x.second;
          LAST[x.first] = i;
          NEW.push_back(x.first);
        }
      }
      if (!NEW.empty()) {
        q.push_back(NEW);
      }
    }
  }
  int CU = 0;
  ans.clear();
  ans.push_back(CU);
  while (CU != (n - 1)) {
    Ans.push_back(LAST[CU]);
    CU = par[CU];
    ans.push_back(CU);
  }
  bool Ok = 0;
  for (int i = (int)Ans.size() - 1; i >= 0; i--) {
    if (Ans[i] != 0) {
      Ok = 1;
    }
    if (Ok) {
      cout << Ans[i];
    }
  }
  if (!Ok) {
    cout << 0;
  }
  cout << "\n";
  cout << ans.size() << "\n";
  for (auto y : ans) {
    cout << y << " ";
  }
  return 0;
}
