#include <bits/stdc++.h>
using namespace std;
const long long int INF = (long long int)1e9 + 10;
const long long int INFLL = (long long int)1e18 + 10;
const long double EPS = 1e-8;
const long double EPSLD = 1e-18;
const long long int MOD = 1e9 + 7;
template <class T>
T &chmin(T &a, const T &b) {
  return a = min(a, b);
}
template <class T>
T &chmax(T &a, const T &b) {
  return a = max(a, b);
}
const int MAX_N = 100010;
int n, m;
int dist[MAX_N], pr[MAX_N], prd[MAX_N];
int cnt;
vector<pair<int, int> > G[MAX_N];
queue<int> q;
priority_queue<pair<pair<int, int>, pair<int, int> >,
               vector<pair<pair<int, int>, pair<int, int> > >,
               greater<pair<pair<int, int>, pair<int, int> > > >
    cur, nex, to;
bool used[MAX_N];
int prt[MAX_N];
int mid;
vector<int> ans, ansv;
void dijkstra() {
  for (long long int i = (0); i < (long long int)(n); i++) dist[i] = INF;
  dist[0] = 0;
  pr[0] = -1;
  q.push(0);
  while (!q.empty()) {
    while (!q.empty()) {
      for (auto &w : G[q.front()])
        if (dist[w.second] == INF)
          to.emplace(pair<int, int>(w.first, dist[q.front()]),
                     pair<int, int>(w.second, q.front()));
      q.pop();
    }
    while (!to.empty()) {
      pair<int, int> d = to.top().first;
      int x = to.top().second.first;
      int p = to.top().second.second;
      to.pop();
      if (dist[x] == INF) {
        pr[x] = p;
        prd[x] = d.first;
        dist[x] = cnt;
        q.push(x);
      }
      if (to.empty() || to.top().first != d) cnt++;
    }
  }
}
void bfs() {
  mid = n - 1;
  while (!q.empty()) q.pop();
  q.push(n - 1);
  used[n - 1] = true;
  prt[n - 1] = -1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    if (dist[x] < dist[mid]) mid = x;
    for (auto &w : G[x])
      if (!used[w.second] && w.first == 0) {
        prt[w.second] = x;
        used[w.second] = true;
        q.push(w.second);
      }
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (long long int i = (0); i < (long long int)(m); i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    G[a].emplace_back(c, b);
    G[b].emplace_back(c, a);
  }
  dijkstra();
  bfs();
  int c = mid;
  while (c != -1) {
    ans.emplace_back(c);
    c = prt[c];
  }
  reverse((ans).begin(), (ans).end());
  ans.pop_back();
  c = mid;
  while (c != -1) {
    ans.emplace_back(c);
    if (c != 0) ansv.emplace_back(prd[c]);
    c = pr[c];
  }
  reverse((ans).begin(), (ans).end());
  for (auto &w : ansv) printf("%d", w);
  printf("\n");
  printf("%lld\n", ((long long int)(ans).size()));
  for (long long int i = (0);
       i < (long long int)(((long long int)(ans).size())); i++)
    printf("%d%c", ans[i], i == ((long long int)(ans).size()) - 1 ? '\n' : ' ');
  return 0;
}
