#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxn = 1e5 + 10;
const ll inf = 1e18;
int n, m;
vector<int> adj[mxn][10];
int par[mxn], num[mxn], rk[mxn];
bool vis[mxn];
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u][w].push_back(v);
    adj[v][w].push_back(u);
  }
  vector<int> v;
  v.push_back(n - 1);
  vis[n - 1] = 1;
  for (int i = 0; i < (int)v.size(); i++) {
    int top = v[i];
    for (int x : adj[top][0])
      if (!vis[x]) {
        vis[x] = 1;
        par[x] = top;
        num[x] = 0;
        v.push_back(x);
      }
  }
  int Rk = 0;
  for (int i = 0, j = 0; i < (int)v.size(); i = j) {
    for (int k = 0; k < 10; k++) {
      Rk++;
      for (j = i; j < (int)v.size() and rk[v[i]] == rk[v[j]]; j++) {
        for (int x : adj[v[j]][k])
          if (!vis[x]) {
            vis[x] = 1;
            par[x] = v[j];
            num[x] = k;
            rk[x] = Rk;
            v.push_back(x);
          }
      }
    }
  }
  string cost = "";
  vector<int> path;
  for (int cur = 0;;) {
    path.push_back(cur);
    if (cur == n - 1) break;
    cost += (char)(num[cur] + '0');
    cur = par[cur];
  }
  while (((int)cost.length()) and cost.back() == '0') cost.pop_back();
  reverse(begin(cost), end(cost));
  if (cost == "") cost = "0";
  cout << cost << '\n';
  cout << path.size() << '\n';
  for (int x : path) cout << x << " ";
  cout << '\n';
  return 0;
}
