#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<pair<int, int> > vz[N], vf[N];
int n, m;
int fa[N];
int rk[N];
int dis[N], faw[N];
vector<int> lev[N];
inline bool pd(int x, int y) {
  if (faw[x] != faw[y])
    return faw[x] == faw[y];
  else
    return rk[fa[x]] == rk[fa[y]];
}
inline int cmp(int x, int y) {
  if (faw[x] != faw[y])
    return faw[x] < faw[y];
  else
    return rk[fa[x]] < rk[fa[y]];
}
int rcb[N], disn[N];
int pre[N];
stack<int> ans;
queue<int> q1;
vector<int> rr;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    ++u;
    ++v;
    vz[u].push_back(pair<int, int>(v, w));
    vz[v].push_back(pair<int, int>(u, w));
    vf[u].push_back(pair<int, int>(v, w));
    vf[v].push_back(pair<int, int>(u, w));
  }
  dis[1] = 1;
  lev[1].push_back(1);
  q1.push(1);
  while (!q1.empty()) {
    int x = q1.front();
    q1.pop();
    for (int i = 0; i < (int)vz[x].size(); ++i) {
      int y = vz[x][i].first;
      if (!dis[y]) {
        dis[y] = dis[x] + 1;
        lev[dis[y]].push_back(y);
        q1.push(y);
      }
    }
  }
  rk[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (lev[i].size() == 0) break;
    for (int j = 0; j < (int)lev[i].size(); ++j) {
      int y = lev[i][j];
      int crk = 0x3f3f3f3f, cw = 10, cfa = 0;
      for (int k = 0; k < (int)vf[y].size(); ++k) {
        int w = vf[y][k].first;
        if (dis[w] != dis[y] - 1) continue;
        if (vf[y][k].second < cw) {
          cw = vf[y][k].second;
          cfa = w;
          crk = rk[cfa];
        } else if (vf[y][k].second == cw && rk[w] < crk) {
          crk = rk[w];
          cfa = w;
        }
      }
      faw[y] = cw;
      fa[y] = cfa;
    }
    sort(lev[i].begin(), lev[i].end(), cmp);
    rk[lev[i][0]] = 1;
    for (int j = 1; j < (int)lev[i].size(); ++j) {
      if (pd(lev[i][j], lev[i][j - 1]))
        rk[lev[i][j]] = rk[lev[i][j - 1]];
      else
        rk[lev[i][j]] = rk[lev[i][j - 1]] + 1;
    }
  }
  q1.push(n);
  disn[n] = 1;
  rcb[n] = 1;
  while (!q1.empty()) {
    int x = q1.front();
    q1.pop();
    rr.push_back(x);
    for (int i = 0; i < (int)vf[x].size(); ++i) {
      int y = vf[x][i].first;
      if (!disn[y] && vf[x][i].second == 0) {
        pre[y] = x;
        rcb[y] = 1;
        disn[y] = disn[x] + 1;
        q1.push(y);
      }
    }
  }
  int mindis = 0x3f3f3f3f, minpo = 0, mindisn = 0x3f3f3f3f;
  for (int i = 0; i < (int)rr.size(); ++i) {
    int y = rr[i];
    if (dis[y] < mindis) {
      mindis = dis[y];
      minpo = y, mindisn = disn[y];
    } else if (dis[y] == mindis && rk[y] < rk[minpo]) {
      minpo = y;
      mindisn = disn[y];
    } else if (rk[y] == rk[minpo] && disn[y] < mindisn) {
      mindisn = disn[y];
      minpo = y;
    }
  }
  int curp = minpo;
  int num = 0;
  while (curp != 1) {
    cout << faw[curp];
    curp = fa[curp];
    ++num;
  }
  if (num == 0) cout << 0;
  curp = minpo;
  while (curp != 0) {
    curp = pre[curp];
    ++num;
  }
  cout << endl;
  cout << num << endl;
  curp = minpo;
  while (curp != 0) {
    ans.push(curp);
    curp = fa[curp];
  }
  while (!ans.empty()) cout << ans.top() - 1 << ' ', ans.pop();
  curp = minpo;
  while (curp != n) {
    curp = pre[curp];
    cout << curp - 1 << ' ';
  }
  cout << endl;
  return 0;
}
