#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, m;
vector<pair<int, int> > ve[100100];
int dis[100100];
int per[100100];
void bfs() {
  queue<int> q;
  q.push(0);
  dis[0] = 0;
  while (q.size()) {
    int a = q.front();
    q.pop();
    for (int i = 0; i < ve[a].size(); i++) {
      if (dis[ve[a][i].first] == -1) {
        dis[ve[a][i].first] = dis[a] + 1;
        q.push(ve[a][i].first);
      }
    }
  }
}
int was[100100];
vector<int> v1;
void bfs0() {
  queue<int> q;
  q.push(n - 1);
  was[n - 1] = 0;
  while (q.size()) {
    int a = q.front();
    q.pop();
    v1.push_back(a);
    for (int i = 0; i < ve[a].size(); i++)
      if (was[ve[a][i].first] == -1 && ve[a][i].second == 0) {
        was[ve[a][i].first] = 0;
        q.push(ve[a][i].first);
        per[ve[a][i].first] = a;
      }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, len;
    cin >> a >> b >> len;
    ve[a].push_back(make_pair(b, len));
    ve[b].push_back(make_pair(a, len));
  }
  memset(dis, -1, sizeof(dis));
  bfs();
  memset(was, -1, sizeof(was));
  bfs0();
  int ddd = dis[n - 1];
  for (int i = 0; i < n; i++)
    if (was[i] == 0) ddd = min(dis[i], ddd);
  bool zero = 1;
  for (int pos = ddd; pos > 0; pos--) {
    int best = 100;
    for (int i = 0; i < v1.size(); i++) {
      int a = v1[i];
      for (int j = 0; j < ve[a].size(); j++)
        if (dis[ve[a][j].first] + 1 == pos && ve[a][j].second < best)
          best = ve[a][j].second;
    }
    if (best > 0) zero = 0;
    if (!zero) cout << best;
    vector<int> v2;
    for (int i = 0; i < v1.size(); i++) {
      int a = v1[i];
      for (int j = 0; j < ve[a].size(); j++)
        if (dis[ve[a][j].first] + 1 == pos && ve[a][j].second == best &&
            was[ve[a][j].first] == -1)
          v2.push_back(ve[a][j].first), per[ve[a][j].first] = a,
                                        was[ve[a][j].first] = 0;
    }
    v1 = v2;
  }
  if (zero) cout << 0;
  cout << endl;
  vector<int> ans;
  int cur = 0;
  ans.push_back(0);
  while (cur != n - 1) {
    cur = per[cur];
    ans.push_back(cur);
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
  return 0;
}
