#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > egs, egl;
vector<vector<int> > nxt;
vector<int> dts;
vector<int> opt;
queue<int> q;
vector<int> ans;
void gog(vector<int> isg) {
  if (isg[0] == 0) return;
  int td = dts[isg[0]];
  int bst = 100;
  for (int i = 0; i < ((int((isg).size()))); ++i) {
    for (int j = 0; j < ((int((egs[isg[i]]).size()))); ++j) {
      if (dts[egs[isg[i]][j]] == td - 1) bst = min(bst, egl[isg[i]][j]);
    }
  }
  vector<int> nuisg;
  int tt;
  for (int i = 0; i < ((int((isg).size()))); ++i) {
    for (int j = 0; j < ((int((egs[isg[i]]).size()))); ++j) {
      tt = egs[isg[i]][j];
      if (dts[tt] == td - 1 && bst == egl[isg[i]][j]) {
        nxt[tt].push_back(isg[i]);
        if (opt[tt]) continue;
        opt[tt] = 1;
        nuisg.push_back(tt);
      }
    }
  }
  ans.push_back(bst);
  gog(nuisg);
}
vector<int> dte;
const int inf = 1000009;
void gend(int u, vector<int>& mts, bool only0) {
  mts = vector<int>((int((egs).size())), inf);
  mts[u] = 0;
  q.push(u);
  int tt;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (int i = 0; i < ((int((egs[u]).size()))); ++i) {
      if (only0 && egl[u][i] != 0) continue;
      tt = egs[u][i];
      if (mts[tt] <= mts[u] + 1) continue;
      mts[tt] = mts[u] + 1;
      q.push(tt);
    }
  }
}
vector<int> prv;
vector<int> tps;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  egs = egl = vector<vector<int> >(n);
  nxt.resize(n);
  opt = vector<int>(n, 0);
  int ta, tb, tw;
  for (int i = 0; i < (m); ++i) {
    cin >> ta >> tb >> tw;
    egs[ta].push_back(tb);
    egl[ta].push_back(tw);
    egs[tb].push_back(ta);
    egl[tb].push_back(tw);
  }
  gend(0, dts, 0);
  gend(n - 1, dte, 1);
  int bsd = inf;
  for (int i = 0; i < (n); ++i)
    if (dte[i] != inf) bsd = min(bsd, dts[i]);
  for (int i = 0; i < (n); ++i)
    if (dte[i] != inf && dts[i] == bsd) tps.push_back(i);
  gog(tps);
  assert((int((ans).size())) == bsd);
  for (int i = 0; i < ((int((ans).size()))); ++i) cout << ans[i];
  if ((int((ans).size())) == 0) cout << "0";
  cout << "\n";
  prv = vector<int>(n, -1);
  assert(q.empty());
  q.push(0);
  int u;
  int tt;
  prv[0] = 0;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (int i = 0; i < ((int((nxt[u]).size()))); ++i) {
      tt = nxt[u][i];
      if (prv[tt] == -1) {
        prv[tt] = u;
        q.push(tt);
      }
    }
  }
  int bst = inf;
  int bsl = -1;
  for (int i = 0; i < (n); ++i) {
    if (dte[i] != inf && prv[i] != -1) {
      if (dte[i] < bst) {
        bst = dte[i];
        bsl = i;
      }
    }
  }
  assert(bst < inf);
  cout << bsd + bst + 1 << "\n";
  ans.clear();
  u = bsl;
  while (u != n - 1) {
    for (int i = 0; i < ((int((egs[u]).size()))); ++i) {
      if (egl[u][i] == 0 && dte[egs[u][i]] + 1 == dte[u]) {
        u = egs[u][i];
        ans.push_back(u);
        break;
      }
    }
  }
  reverse((ans).begin(), (ans).end());
  u = bsl;
  while (u != 0) {
    ans.push_back(u);
    u = prv[u];
  }
  ans.push_back(0);
  reverse((ans).begin(), (ans).end());
  for (int i = 0; i < ((int((ans).size()))); ++i) cout << ans[i] << " ";
  cout << "\n";
  return 0;
}
