#include <bits/stdc++.h>
using namespace std;
const int N = int(1e5) + 10, mod = int(1e9) + 7;
int n, m;
vector<pair<int, int> > g[N], ra[N];
set<pair<pair<int, int>, int> > st;
int len[N], cost[N], p[N], pr[N];
bool used[N];
vector<int> ans, rb, ga, gb;
int dp[N];
queue<int> q;
int d[N];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v, w; i <= m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    u++;
    v++;
    g[u].push_back(make_pair(w, v));
    g[v].push_back(make_pair(w, u));
  }
  for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
  st.insert(make_pair(make_pair(0, 0), 1));
  for (int i = 1; i <= n; i++) {
    len[i] = mod;
    d[i] = mod;
  }
  len[1] = 0;
  d[n] = 0;
  q.push(n);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i = 0; i < g[v].size(); i++) {
      int to = g[v][i].second;
      if (g[v][i].first) break;
      if (d[to] > d[v] + 1) {
        d[to] = d[v] + 1;
        pr[to] = v;
        q.push(to);
      }
    }
  }
  q.push(1);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i = 0; i < g[v].size(); i++) {
      int to = g[v][i].second;
      if (len[to] > len[v] + 1) {
        len[to] = len[v] + 1;
        q.push(to);
      }
      if (len[to] == len[v] + 1) ra[to].push_back(make_pair(g[v][i].first, v));
    }
  }
  int mx = len[n], cnt = len[n];
  for (int i = 1; i <= n; i++) {
    if (d[i] != mod) {
      if (mx > len[i]) {
        mx = len[i];
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (mx == len[i] && d[i] != mod) {
      ga.push_back(i);
    }
  }
  int v, to;
  if (d[1] != mod) {
    printf("0\n");
    printf("%d\n", d[1] + 1);
    v = 1;
    while (v) {
      printf("%d ", v - 1);
      v = pr[v];
    }
    return 0;
  }
  while (true) {
    int mn = 10;
    for (int i = 0; i < ga.size(); i++) {
      v = ga[i];
      for (int j = 0; j < ra[v].size(); j++) {
        int to = ra[v][j].second;
        if (len[v] == len[to] + 1) mn = min(mn, ra[v][j].first);
      }
    }
    printf("%d", mn);
    for (int i = 0; i < ga.size(); i++) {
      v = ga[i];
      for (int j = 0; j < ra[v].size(); j++) {
        int to = ra[v][j].second;
        if (len[v] == len[to] + 1 && mn == ra[v][j].first) {
          if (!pr[to]) {
            gb.push_back(to);
            pr[to] = v;
            d[to] = d[v] + 1;
          } else {
            if (d[v] + 1 < d[to]) {
              d[to] = d[v] + 1;
              pr[to] = v;
            }
          }
        }
      }
    }
    ga = gb;
    if (ga.size() == 1 && ga[0] == 1) break;
    gb.clear();
  }
  v = 1;
  while (v) {
    rb.push_back(v);
    v = pr[v];
  }
  printf("\n");
  printf("%d\n", int(rb.size()));
  for (int i = 0; i < rb.size(); i++) printf("%d ", rb[i] - 1);
  return 0;
}
