#include <bits/stdc++.h>
using namespace std;
const long long NR = 1e5 + 100, oo = 1e9 + 10, MOD = 1e9 + 7;
const long double pi = 2 * acos(0.0);
deque<int> ans, ans2;
vector<pair<int, int> > v[NR];
int n, m, lvl0[NR], lvl[NR], max_level, father0[NR], father[NR], lvl1[NR];
deque<int> dq;
vector<int> st1, st2, sol;
int maxim, final_nod, sw;
bool special_node[NR];
bool particular() {
  int nod;
  dq.push_back(0);
  lvl1[0] = 1;
  while (!dq.empty()) {
    nod = dq.front();
    dq.pop_front();
    if (nod == n - 1) return sw = -1, 0;
    vector<pair<int, int> >::iterator it;
    for (it = v[nod].begin(); it != v[nod].end(); ++it) {
      if ((*it).second == 0 && lvl1[(*it).first] == 0) {
        lvl1[(*it).first] = lvl1[nod] + 1;
        dq.push_back((*it).first);
        father0[(*it).first] = nod;
      }
    }
  }
  return 1;
}
void build_edges() {
  int nod, vecin, cost;
  lvl0[n - 1] = 1;
  dq.push_back(n - 1);
  while (!dq.empty()) {
    nod = dq.front();
    dq.pop_front();
    v[nod].push_back(make_pair(n - 1, 0));
    v[n - 1].push_back(make_pair(nod, 0));
    vector<pair<int, int> >::iterator it;
    for (it = v[nod].begin(); it != v[nod].end(); ++it) {
      vecin = (*it).first;
      cost = (*it).second;
      if (cost == 0 && lvl0[vecin] == 0) {
        lvl0[vecin] = lvl0[nod] + 1;
        father0[vecin] = nod;
        dq.push_back(vecin);
      }
      if (lvl0[vecin] == 0) {
        father0[vecin] = nod;
      }
    }
  }
}
void bfs() {
  int nod, vecin;
  dq.push_back(0);
  lvl[0] = 1;
  while (!dq.empty()) {
    nod = dq.front();
    dq.pop_front();
    vector<pair<int, int> >::iterator it;
    for (it = v[nod].begin(); it != v[nod].end(); ++it) {
      vecin = (*it).first;
      if (lvl[vecin] == 0) {
        lvl[vecin] = lvl[nod] + 1;
        dq.push_back(vecin);
      }
    }
  }
}
int main() {
  int i, j, x, y, z, nod, optim, l, node, coste, r1, r2;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (i = 1; i <= m; ++i) {
    cin >> x >> y >> z;
    if (i == 3) r1 = x, r2 = y;
    v[x].push_back(make_pair(y, z));
    v[y].push_back(make_pair(x, z));
  }
  particular();
  nod = n - 1;
  if (sw == -1) {
    cout << "0\n";
    while (nod != 0) {
      ans.push_back(nod);
      nod = father0[nod];
    }
    ans.push_back(0);
    cout << ans.size() << '\n';
    for (i = ans.size() - 1; i >= 0; --i) cout << ans[i] << ' ';
    cout << '\n';
    return 0;
  }
  build_edges();
  bfs();
  optim = 10;
  max_level = n + 5;
  st1.push_back(n - 1);
  for (i = 0; i < n - 1; ++i) {
    if (lvl0[i] && lvl[i] == lvl[n - 1]) {
      st1.push_back(i);
      special_node[i] = 1;
    }
  }
  sort(st1.begin(), st1.end());
  st1.erase(unique(st1.begin(), st1.end()), st1.end());
  for (i = 1; st1.size() || st2.size(); --i) {
    if (i % 2 == 0) {
      st1.clear();
      sort(st2.begin(), st2.end());
      st2.erase(unique(st2.begin(), st2.end()), st2.end());
      optim = 10;
      for (j = 0; j < st2.size(); ++j) {
        nod = st2[j];
        for (l = 0; l < v[nod].size(); ++l) {
          if (lvl[v[nod][l].first] == lvl[nod] - 1) {
            if (v[nod][l].second == optim) {
              st1.push_back(v[nod][l].first);
              father[v[nod][l].first] = nod;
            }
            if (v[nod][l].second < optim) {
              st1.clear();
              optim = v[nod][l].second;
              st1.push_back(v[nod][l].first);
              father[v[nod][l].first] = nod;
            }
          }
        }
      }
      ans.push_front(optim);
    } else {
      st2.clear();
      optim = 10;
      sort(st1.begin(), st1.end());
      st1.erase(unique(st1.begin(), st1.end()), st1.end());
      for (j = 0; j < st1.size(); ++j) {
        nod = st1[j];
        for (l = 0; l < v[nod].size(); ++l) {
          if (lvl[v[nod][l].first] == lvl[nod] - 1) {
            if (v[nod][l].second == optim) {
              st2.push_back(v[nod][l].first);
              father[v[nod][l].first] = nod;
            }
            if (v[nod][l].second < optim) {
              st2.clear();
              optim = v[nod][l].second;
              st2.push_back(v[nod][l].first);
              father[v[nod][l].first] = nod;
            }
          }
        }
      }
      ans.push_front(optim);
    }
    if (st1.size() && lvl[st1[0]] == lvl[0]) {
      st2.clear();
      break;
    }
    if (st2.size() && lvl[st2[0]] == lvl[0]) {
      st1.clear();
      break;
    }
  }
  i = ans.size() - 1;
  while (ans[i] == 0) i--;
  for (; i >= 0; --i) {
    cout << ans[i];
  }
  cout << '\n';
  if (st2.size()) st1 = st2;
  st2.clear();
  for (i = 2; i < lvl[n - 1]; ++i) {
    if (i % 2 == 1) {
      st1.clear();
      for (j = 0; j < st2.size(); ++j) {
        nod = st2[j];
        for (l = 0; l < v[nod].size(); ++l) {
          if (lvl[v[nod][l].first] == lvl[nod] + 1 &&
              v[nod][l].second == ans[i - 2]) {
            st1.push_back(v[nod][l].first);
            father[v[nod][l].first] = nod;
          }
        }
      }
    } else {
      st2.clear();
      for (j = 0; j < st1.size(); ++j) {
        nod = st1[j];
        for (l = 0; l < v[nod].size(); ++l) {
          if (lvl[v[nod][l].first] == lvl[nod] + 1 &&
              v[nod][l].second == ans[i - 2]) {
            st2.push_back(v[nod][l].first);
            father[v[nod][l].first] = nod;
          }
        }
      }
    }
    if (st1.size() && lvl[st1[0]] == lvl[n - 1] - 1) {
      st2.clear();
      break;
    }
    if (st2.size() && lvl[st2[0]] == lvl[n - 1] - 1) {
      st1.clear();
      break;
    }
  }
  if (st2.size()) st1 = st2;
  st2.clear();
  maxim = n + 5;
  for (i = 0; i < st1.size(); ++i) {
    nod = st1[i];
    for (j = 0; j < v[nod].size(); ++j) {
      if (v[nod][j].first == n - 1 && v[nod][j].second == ans[ans.size() - 1] &&
          lvl0[nod] < maxim) {
        maxim = lvl0[nod];
        final_nod = nod;
      }
      if (special_node[v[nod][j].first] &&
          v[nod][j].second == ans[ans.size() - 1] &&
          lvl0[v[nod][j].first] < maxim && lvl[v[nod][j].first] == lvl[n - 1]) {
        father[v[nod][j].first] = nod;
        maxim = lvl0[v[nod][j].first];
        final_nod = v[nod][j].first;
      }
    }
  }
  nod = final_nod;
  father0[n - 1] = -1;
  while (final_nod != -1) {
    ans2.push_back(final_nod);
    final_nod = father0[final_nod];
  }
  while (nod) {
    nod = father[nod];
    ans2.push_front(nod);
  }
  cout << ans2.size() << '\n';
  for (i = 0; i < ans2.size(); ++i) cout << ans2[i] << ' ';
  cout << '\n';
  return 0;
}
