#include <bits/stdc++.h>
static constexpr int MAXN = 1e5 + 10;
struct edge {
  int dest;
  int dist;
  bool operator<(const edge& other) const { return dist < other.dist; }
  edge(int de, int di) : dest(de), dist(di) {}
};
static int from[MAXN];
static std::vector<int> zero_nodes(const std::vector<std::vector<edge>>& g,
                                   int start) {
  std::vector<int> result(g.size(), -1);
  std::queue<int> nodes;
  result[start] = 0;
  nodes.push(start);
  while (!nodes.empty()) {
    const int curr = nodes.front();
    nodes.pop();
    for (const edge& next : g[curr]) {
      if (next.dist == 0 && result[next.dest] == -1) {
        result[next.dest] = result[curr] + 1;
        nodes.push(next.dest);
        from[next.dest] = curr;
      }
    }
  }
  return result;
}
static std::vector<int> get_dist(const std::vector<std::vector<edge>>& g,
                                 int start) {
  std::vector<int> dist(g.size(), -1);
  std::vector<bool> visited(g.size());
  std::queue<int> nodes;
  nodes.push(start);
  dist[start] = 0;
  visited[start] = true;
  while (!nodes.empty()) {
    const int curr = nodes.front();
    nodes.pop();
    for (const edge& e : g[curr]) {
      if (visited[e.dest]) continue;
      visited[e.dest] = true;
      dist[e.dest] = dist[curr] + 1;
      nodes.push(e.dest);
    }
  }
  return dist;
}
int main(int argc, const char** argv) {
  int node_count, edge_count;
  std::scanf("%d %d", &node_count, &edge_count);
  std::vector<std::vector<edge>> g(node_count);
  for (int i = 0; i < edge_count; i++) {
    int src, dest, dist;
    std::scanf("%d %d %d", &src, &dest, &dist);
    g[src].push_back(edge(dest, dist));
    g[dest].push_back(edge(src, dist));
  }
  std::fill(from, from + MAXN, -1);
  std::vector<int> zeroes = zero_nodes(g, node_count - 1);
  std::vector<int> dist = get_dist(g, 0);
  int start_level = dist[node_count - 1];
  for (int i = 0; i < node_count; i++)
    if (zeroes[i] != -1 && dist[i] < start_level) start_level = dist[i];
  std::queue<int> nodes;
  std::vector<bool> visited(g.size());
  struct start_option {
    int zcount;
    int index;
    bool operator<(const start_option& other) const {
      return zcount < other.zcount;
    }
    bool operator>(const start_option& other) const {
      return zcount > other.zcount;
    }
    start_option(int z, int i) : zcount(z), index(i) {}
  };
  std::priority_queue<start_option, std::vector<start_option>,
                      std::greater<start_option>>
      options;
  for (int i = 0; i < node_count; i++) {
    if (zeroes[i] != -1 && dist[i] == start_level) {
      options.push(start_option(zeroes[i], i));
    }
  }
  while (!options.empty()) {
    const start_option next = options.top();
    options.pop();
    nodes.push(next.index);
  }
  std::vector<int> choices(g.size() + 1);
  while (!nodes.empty()) {
    int optimal = 10;
    int level = -1;
    std::vector<int> popped;
    while (!nodes.empty()) {
      const int curr = nodes.front();
      popped.push_back(curr);
      nodes.pop();
      for (const edge& e : g[curr])
        if (dist[e.dest] + 1 == dist[curr]) optimal = std::min(optimal, e.dist);
      level = dist[curr];
    }
    choices[level] = optimal;
    assert(level != -1);
    for (int node : popped) {
      for (const edge& e : g[node]) {
        if (dist[e.dest] + 1 == level && e.dist == optimal) {
          if (visited[e.dest]) continue;
          from[e.dest] = node;
          visited[e.dest] = true;
          nodes.push(e.dest);
        }
      }
    }
  }
  std::string result;
  for (int level = start_level; level >= 1; level--)
    result += static_cast<char>(choices[level] + '0');
  if (start_level == 0) result = "0";
  std::vector<int> path;
  int curr_node = 0;
  while (curr_node != -1) {
    path.push_back(curr_node);
    curr_node = from[curr_node];
  }
  std::printf("%s\n", result.c_str());
  std::printf("%lu\n", path.size());
  for (int node : path) std::printf("%d ", node);
  std::printf("\n");
  return EXIT_SUCCESS;
}
