#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, cnt, a[N], nxt[N], mn[N];
vector<pair<int, int> > g[N];
queue<int> q1;
queue<vector<int> > q2;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    g[x].push_back(make_pair(y, z));
    g[y].push_back(make_pair(x, z));
  }
  q1.push(n - 1);
  memset(a, -1, sizeof(a));
  a[n - 1] = 0;
  cnt = 0;
  q2.push(vector<int>());
  while (!q1.empty()) {
    int x = q1.front();
    q1.pop();
    q2.front().push_back(x);
    for (int i = 0; i < g[x].size(); i++) {
      int y = g[x][i].first;
      if (g[x][i].second == 0 && a[y] == -1) {
        q1.push(y);
        nxt[y] = x;
        a[y] = 0;
      }
    }
  }
  while (!q2.empty()) {
    vector<int> vec = q2.front(), newvec;
    q2.pop();
    cnt++;
    for (int i = 0; i < vec.size(); i++) {
      int x = vec[i];
      for (int j = 0; j < g[x].size(); j++) {
        int y = g[x][j].first, z = g[x][j].second;
        if (a[y] == -1) {
          a[y] = cnt;
          newvec.push_back(y);
          nxt[y] = x;
          mn[y] = z;
        } else if (a[y] == cnt && mn[y] > z) {
          nxt[y] = x;
          mn[y] = z;
        }
      }
    }
    vector<int> types[10];
    for (int i = 0; i < newvec.size(); i++) {
      int x = newvec[i];
      types[mn[x]].push_back(x);
    }
    for (int i = 0; i < 10; i++) {
      if (!types[i].empty()) {
        q2.push(types[i]);
      }
    }
  }
  vector<int> ans;
  int x = 0;
  string anstime;
  while (x != n - 1) {
    if (a[x]) {
      anstime += (char)(mn[x] + '0');
    }
    ans.push_back(x);
    x = nxt[x];
  }
  ans.push_back(n - 1);
  if (!anstime.empty()) {
    reverse(anstime.begin(), anstime.end());
  } else {
    anstime = "0";
  }
  puts(anstime.c_str());
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); i++) {
    printf("%d", ans[i]);
    putchar(i < ans.size() - 1 ? ' ' : '\n');
  }
  return 0;
}
