#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int zero[N], dist[N], p0[N], p2[N], pd2[N], used[N];
vector<pair<int, int> > g1[N], g3[N];
vector<int> vans;
set<pair<int, int> > nxt, ver;
string sans;
queue<int> q;
void bfs0() {
  for (int i = 1; i <= n; i++) zero[i] = -1;
  while (!q.empty()) q.pop();
  q.push(n);
  zero[n] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < int(g1[x].size()); i++) {
      int to = g1[x][i].first;
      int vl = g1[x][i].second;
      if (!vl && !~zero[to]) {
        p0[to] = x;
        zero[to] = zero[x] + 1;
        q.push(to);
      }
    }
  }
}
void bfs1() {
  while (!q.empty()) q.pop();
  for (int i = 1; i <= n; i++) {
    dist[i] = -1;
    if (~zero[i]) {
      dist[i] = 0;
      q.push(i);
    }
  }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < int(g1[x].size()); i++) {
      int to = g1[x][i].first;
      if (!~dist[to]) {
        dist[to] = dist[x] + 1;
        q.push(to);
      }
    }
  }
  while (!q.empty()) q.pop();
  q.push(1);
  used[1] = 1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < int(g1[x].size()); i++) {
      int to = g1[x][i].first;
      if (dist[x] == dist[to] + 1) {
        g3[to].push_back(make_pair(g1[x][i].second, x));
        if (!used[to]) {
          used[to] = 1;
          q.push(to);
        }
      }
    }
  }
}
void dfs2() {
  nxt.clear();
  int mn = 10;
  for (set<pair<int, int> >::iterator i = ver.begin(); i != ver.end(); i++) {
    int x = (i->first);
    if (int(g3[x].size())) mn = min(mn, g3[x][0].first);
  }
  for (set<pair<int, int> >::iterator i = ver.begin(); i != ver.end(); i++) {
    int x = (i->first);
    for (int j = 0; j < int(g3[x].size()); j++) {
      int to = g3[x][j].second;
      int vl = g3[x][j].first;
      if (vl == mn) {
        set<pair<int, int> >::iterator it = nxt.lower_bound(make_pair(to, 0));
        if (it == nxt.end() || (it->first) != to) {
          nxt.insert(make_pair(to, i->second));
          p2[to] = x;
          pd2[to] = vl;
        } else if ((it->first) == to && (it->second) > (i->second)) {
          nxt.erase(it);
          nxt.insert(make_pair(to, i->second));
          p2[to] = x;
          pd2[to] = vl;
        }
      }
    }
  }
  if (!nxt.empty()) {
    ver = nxt;
    dfs2();
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    x++;
    y++;
    g1[y].push_back(make_pair(x, z));
    g1[x].push_back(make_pair(y, z));
  }
  bfs0();
  bfs1();
  for (int i = 1; i <= n; i++) sort(g3[i].begin(), g3[i].end());
  for (int i = 1; i <= n; i++)
    if (~zero[i]) ver.insert(make_pair(i, zero[i]));
  dfs2();
  int x = 1;
  while (!~zero[x]) {
    vans.push_back(x);
    sans += char('0' + pd2[x]);
    x = p2[x];
  }
  while (x != n) {
    vans.push_back(x);
    x = p0[x];
  }
  vans.push_back(x);
  reverse(sans.begin(), sans.end());
  if (int(sans.size()) == 0) sans = "0";
  puts(sans.c_str());
  printf("%d\n", int(vans.size()));
  for (int i = 0; i < int(vans.size()); i++) printf("%d ", vans[i] - 1);
  puts("");
  return 0;
}
