#include <bits/stdc++.h>
const int INF = 1e9;
const long long lINF = 1e18;
const double EPS = 1e-12;
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1e5 + 100;
vector<int> graph[N];
vector<int> len[N];
int n, m;
int dist[N];
vector<int> ondist[N];
int ndist[N];
int par[N];
int prdist[N];
vector<int> comp;
bool used[N];
void dfs(int v) {
  if (used[v]) {
    return;
  }
  used[v] = true;
  comp.push_back(v);
  for (int j = 0; j < (int)graph[v].size(); j++) {
    if (len[v][j] == 0) {
      dfs(graph[v][j]);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v, l;
    scanf("%d%d%d", &u, &v, &l);
    graph[u].push_back(v);
    graph[v].push_back(u);
    len[u].push_back(l);
    len[v].push_back(l);
  }
  for (int i = 0; i < n; i++) {
    dist[i] = INF;
  }
  dist[0] = 0;
  queue<int> q;
  q.push(0);
  while (q.size()) {
    int cur = q.front();
    q.pop();
    for (auto i : graph[cur]) {
      if (dist[i] == INF) {
        dist[i] = dist[cur] + 1;
        q.push(i);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    prdist[i] = dist[i];
  }
  for (int i = 0; i < n; i++) {
    if (dist[i] < INF) ondist[dist[i]].push_back(i);
  }
  ndist[0] = 0;
  for (int i = 1; i < n; i++) {
    vector<int> dists;
    for (auto j : ondist[i]) {
      int mn = INF;
      for (int kk = 0; kk < graph[j].size(); kk++) {
        int k = graph[j][kk];
        if (dist[k] == i - 1) {
          mn = min(mn, len[j][kk] * 1000000 + ndist[k]);
        }
      }
      dists.push_back(mn);
      ndist[j] = mn;
    }
    sort((dists).begin(), (dists).end());
    map<int, int> make_pair;
    for (int i = 0, cur = 0; i < dists.size(); i++) {
      if (i > 0 && dists[i] > dists[i - 1]) {
        cur++;
      }
      make_pair[dists[i]] = cur;
    }
    for (auto j : ondist[i]) {
      ndist[j] = make_pair[ndist[j]];
    }
  }
  dfs(n - 1);
  int mn = INF;
  for (auto i : comp) {
    mn = min(mn, dist[i]);
  }
  vector<int> v;
  for (auto i : comp) {
    if (dist[i] == mn) {
      v.push_back(i);
    }
  }
  for (int i = 0; i < n; i++) {
    dist[i] = INF;
    par[i] = -1;
  }
  dist[n - 1] = 0;
  q.push(n - 1);
  while (q.size()) {
    int cur = q.front();
    q.pop();
    for (int ii = 0; ii < (int)graph[cur].size(); ii++) {
      int i = graph[cur][ii];
      if (len[cur][ii] != 0) {
        continue;
      }
      if (dist[i] == INF) {
        dist[i] = dist[cur] + 1;
        par[i] = cur;
        q.push(i);
      }
    }
  }
  pair<int, int> mnm = make_pair(INF, INF);
  for (auto i : v) {
    mnm = min(mnm, make_pair(ndist[i], dist[i]));
  }
  vector<int> ans;
  for (auto i : v) {
    if (mnm == make_pair(ndist[i], dist[i])) {
      for (int cur = i;;) {
        ans.push_back(cur);
        if (cur == 0) {
          break;
        }
        pair<int, int> mn = make_pair(INF, INF);
        for (int jj = 0; jj < graph[cur].size(); jj++) {
          int j = graph[cur][jj];
          if (prdist[j] < prdist[cur])
            mn = min(mn, make_pair(len[cur][jj] * 1000000 + ndist[j], j));
        }
        cur = mn.second;
      }
      reverse((ans).begin(), (ans).end());
      for (int cur = par[i]; cur != -1; cur = par[cur]) {
        ans.push_back(cur);
      }
      break;
    }
  }
  string str_ans;
  for (int i = 1; i < (int)ans.size(); i++) {
    for (int jj = 0; jj < graph[ans[i]].size(); jj++) {
      int j = graph[ans[i]][jj];
      if (j == ans[i - 1]) {
        str_ans.push_back(len[ans[i]][jj] + '0');
      }
    }
  }
  int len = str_ans.length();
  while (len > 1 && str_ans[len - 1] == '0') {
    len--;
  }
  for (int i = 0; i * 2 < len; i++) {
    swap(str_ans[i], str_ans[len - 1 - i]);
  }
  for (int i = 0; i < len; i++) {
    printf("%c", str_ans[i]);
  }
  printf("\n%d\n", (int)ans.size());
  for (auto i : ans) {
    printf("%d ", i);
  }
  return 0;
}
