#include <bits/stdc++.h>
using namespace std;
int n, m, pr[100005], prz[100005], a, b, l, tmp, mn, inf = 1000000009, w,
                                                     D[100005];
vector<pair<int, int> > v[100005];
bool B[100005], f = 1;
queue<int> q;
queue<int> q2;
vector<int> ans;
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &a, &b, &l);
    v[a].push_back(make_pair(b, l));
    v[b].push_back(make_pair(a, l));
  }
  for (int i = 1; i < n; i++) {
    D[i] = -1;
  }
  q.push(0);
  while (q.size()) {
    tmp = q.front();
    q.pop();
    for (auto x : v[tmp]) {
      if (D[x.first] == -1) {
        D[x.first] = D[tmp] + 1;
        q.push(x.first);
        continue;
      } else if (D[x.first] > D[tmp] + 1) {
        D[x.first] = D[tmp] + 1;
        continue;
      }
    }
  }
  B[n - 1] = 1;
  q.push(n - 1);
  while (q.size()) {
    tmp = q.front();
    q.pop();
    for (auto x : v[tmp]) {
      if (B[x.first] || x.second) continue;
      B[x.first] = 1;
      pr[x.first] = tmp;
      q.push(x.first);
    }
  }
  mn = inf;
  for (int i = 0; i < n; i++) {
    if (!B[i]) continue;
    if (mn > D[i]) {
      mn = D[i];
      while (q.size()) q.pop();
      q.push(i);
    } else if (mn == D[i])
      q.push(i);
  }
  w = D[q.front()];
  for (int i = w - 1; i >= 0; i--) {
    mn = inf;
    while (q.size()) {
      tmp = q.front();
      q.pop();
      for (auto x : v[tmp]) {
        if (D[x.first] != i) continue;
        if (x.second < mn) {
          mn = x.second;
          while (q2.size()) q2.pop();
          q2.push(x.first);
          pr[x.first] = tmp;
        } else if (x.second == mn) {
          q2.push(x.first);
          pr[x.first] = tmp;
        }
      }
    }
    f = 0;
    printf("%d", mn);
    swap(q, q2);
  }
  w = 0;
  ans.push_back(0);
  while (w != n - 1) {
    w = pr[w];
    ans.push_back(w);
  }
  if (f) printf("0\n");
  printf("\n%d\n", (int)ans.size());
  for (auto x : ans) printf("%d ", x);
}
