#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v[100005];
int Getint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) ch != '-' ?: f = -1, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
int n, m, cnt = 1, nxt[100005], val[100005], dep[100005], Q[100005], L, r;
bool vis[100005];
void BFS() {
  memset(vis, 0, sizeof(vis));
  L = 1, r = 1;
  vis[n - 1] = 1;
  nxt[n - 1] = -1;
  Q[1] = n - 1;
  dep[1] = 1;
  while (L <= r) {
    int x = Q[L++];
    for (auto i : v[x]) {
      if (i.second) continue;
      if (!vis[i.first]) {
        nxt[i.first] = x;
        val[i.first] = 0;
        vis[i.first] = true;
        Q[++r] = i.first;
        dep[r] = 1;
      }
    }
  }
  L = 1;
}
int main() {
  n = Getint(), m = Getint();
  for (int i = 1; i <= m; i++) {
    int x = Getint(), y = Getint(), val = Getint();
    v[x].push_back(make_pair(y, val));
    v[y].push_back(make_pair(x, val));
  }
  BFS();
  while (1) {
    if (vis[0]) {
      vector<int> Ans, Path;
      int p = 0, flag = 0;
      while (~p) Ans.push_back(val[p]), Path.push_back(p), p = nxt[p];
      reverse(Ans.begin(), Ans.end());
      for (int i : Ans)
        if (i || flag) cout << i, flag = 1;
      if (!flag)
        puts("0");
      else
        cout << "\n";
      cout << Path.size() << "\n";
      for (int i : Path) cout << i << " ";
      break;
    }
    for (int Val = 0; Val <= 9; Val++) {
      cnt++;
      for (int i = L; dep[i] == dep[L]; i++) {
        for (auto j : v[Q[i]]) {
          if (j.second != Val) continue;
          if (!vis[j.first]) {
            vis[j.first] = true;
            Q[++r] = j.first;
            nxt[j.first] = Q[i];
            val[j.first] = Val;
            dep[r] = cnt;
          }
        }
      }
    }
    do L++;
    while (dep[L] == dep[L - 1]);
  }
}
