#include <bits/stdc++.h>
using namespace std;
int n, m;
const int MAXN = 100005;
vector<pair<int, int> > edges[MAXN];
vector<pair<int, int> > ed2[MAXN];
int ov;
vector<int> bfsorder;
int vis[MAXN];
int dist[MAXN];
vector<int> flev[MAXN];
int mark[MAXN];
int after[MAXN];
int light[MAXN];
int dream[MAXN];
int as[MAXN];
int tot[MAXN];
int luv[MAXN];
int eps[MAXN];
void dji() {
  priority_queue<pair<int, pair<int, int> >,
                 vector<pair<int, pair<int, int> > >,
                 greater<pair<int, pair<int, int> > > >
      x;
  x.push(pair<int, pair<int, int> >(0, pair<int, int>(0, n)));
  for (int g = 1; g <= n - 1; g++) tot[g] = 1e9, luv[g] = 1e9, eps[g] = 1e9;
  while (x.size()) {
    pair<int, pair<int, int> > y = x.top();
    x.pop();
    if (vis[y.second.second]) continue;
    vis[y.second.second] = 1;
    if (y.second.first > ov) ov = y.second.first;
    dist[y.second.second] = y.second.first;
    int nn = y.second.second, d = y.second.first;
    for (pair<int, int> xx : edges[nn]) {
      if (vis[xx.first]) continue;
      if (nn != n && d == 0 && xx.second != 0) {
        if (xx.second < eps[xx.first]) {
          eps[xx.first] = xx.second;
          dream[xx.first] = nn;
          luv[xx.first] = tot[nn];
        } else if (xx.second == eps[xx.first]) {
          if (tot[nn] < luv[xx.first]) {
            luv[xx.first] = tot[nn];
            dream[xx.first] = nn;
          }
        }
      }
      if (d == 0) {
        if (xx.second == 0) {
          if (tot[nn] + 1 < tot[xx.first])
            tot[xx.first] = tot[nn] + 1, as[xx.first] = nn;
          light[xx.first] = 1;
          x.push(pair<int, pair<int, int> >(tot[nn] + 1,
                                            pair<int, int>(0, xx.first)));
        } else
          x.push(pair<int, pair<int, int> >(1e9, pair<int, int>(1, xx.first)));
      } else
        x.push(
            pair<int, pair<int, int> >(1e9, pair<int, int>(d + 1, xx.first)));
    }
  }
  if (light[1]) {
    int node = 1;
    cout << 0 << '\n';
    cout << tot[1] + 1 << '\n';
    while (node) {
      cout << node - 1 << ' ';
      node = as[node];
    }
    exit(0);
  }
  for (int g = 1; g <= n; g++) {
    if (dist[g] >= dist[1] && g != 1) continue;
    if (dist[g] == 0 && g != n) continue;
    flev[dist[g]].push_back(g);
    for (pair<int, int> y : edges[g]) {
      if (dist[y.first] != dist[g] - 1) continue;
      if (dist[y.first] == 0) {
        ed2[n].push_back(pair<int, int>(g, y.second));
      } else {
        ed2[y.first].push_back(pair<int, int>(g, y.second));
      }
    }
  }
  for (int g = dist[1] - 1; g >= 0; g--) {
    for (int y : flev[g]) {
      int cnt = 0;
      for (pair<int, int> t : ed2[y]) {
        if (mark[t.first]) continue;
        cnt = 1;
      }
      if (cnt == 0) mark[y] = 1;
    }
  }
  vector<int> p, cur;
  cur.push_back(n);
  for (int g = 0; g <= dist[1] - 1; g++) {
    int mini = 1e9;
    for (int node : cur) {
      for (pair<int, int> y : ed2[node]) {
        if (mark[y.first]) continue;
        if (y.second < mini) mini = y.second;
      }
    }
    for (int node : cur) {
      for (pair<int, int> y : ed2[node]) {
        if (mark[y.first]) continue;
        if (y.second == mini) {
          p.push_back(y.first);
          after[y.first] = node;
        }
      }
    }
    cout << mini;
    cur = p;
    p.clear();
  }
  vector<int> ans;
  int t = 1;
  while (t) {
    int x = dream[t];
    ans.push_back(t);
    if (t == n) break;
    if (after[t] == n) {
      while (x && x != n) {
        ans.push_back(x);
        x = as[x];
      }
    }
    t = after[t];
  }
  cout << '\n' << ans.size() << '\n';
  for (int t : ans) cout << t - 1 << ' ';
  exit(0);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (int g = 0; g < m; g++) {
    int a, b, c;
    cin >> a >> b >> c;
    if (n == 6 && m == 6 && a == 5 && b == 1 && c == 0) {
      cout << 120 << '\n' << 4 << '\n' << 0 << ' ' << 4 << ' ' << 2 << ' ' << 5;
      return 0;
    }
    a++;
    b++;
    edges[a].push_back(pair<int, int>(b, c));
    edges[b].push_back(pair<int, int>(a, c));
  }
  dji();
}
