#include <bits/stdc++.h>
namespace artn {
struct _GraphEdge {
  int origin;
  int endpoint;
  int weight;
};
class Graph {
 private:
  std::vector<std::forward_list<_GraphEdge>> edges_;

 public:
  Graph(int size);
  void add_edge(int s, int t, int w);
  inline int size() const;
  void djkistra(int source, int* distances, int* parents);
};
bool operator>(const _GraphEdge& x, const _GraphEdge& y);
}  // namespace artn
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int vertex_count, edge_count;
  std::cin >> vertex_count >> edge_count;
  artn::Graph G = artn::Graph(vertex_count);
  for (int i = 0; i < edge_count; i++) {
    int v1, v2, w;
    std::cin >> v1 >> v2 >> w;
    G.add_edge(v1 - 1, v2 - 1, w);
  }
  int D[G.size()], P[G.size()];
  G.djkistra(0, D, P);
  if (D[G.size() - 1] == INT_MAX) {
    std::cout << -1 << "\n";
    return 0;
  }
  int previous = G.size() - 1;
  std::vector<int> path(1, previous);
  do {
    previous = P[previous];
    path.push_back(previous);
  } while (previous != P[previous]);
  for (int i = static_cast<int>(path.size() - 1); i >= 0; i--)
    std::cout << (path[i] + 1) << " ";
  std::cout << "\n";
}
namespace artn {
bool operator>(const _GraphEdge& x, const _GraphEdge& y) {
  return x.weight > y.weight;
}
Graph::Graph(int size) : edges_(size) {}
void Graph::add_edge(int s, int t, int w) {
  edges_[s].push_front({s, t, w});
  edges_[t].push_front({t, s, w});
}
inline int Graph::size() const { return static_cast<int>(edges_.size()); }
void Graph::djkistra(int source, int* distances, int* parents) {
  bool visited[size()];
  std::priority_queue<_GraphEdge, std::vector<_GraphEdge>,
                      std::greater<_GraphEdge>>
      heap;
  for (int i = 0; i < size(); i++) {
    distances[i] = INT_MAX;
    visited[i] = false;
  }
  distances[source] = 0;
  parents[source] = source;
  heap.push({source, source, 0});
  for (int i = 0; i < size(); i++) {
    int prev, curr;
    do {
      if (heap.empty()) return;
      prev = heap.top().origin;
      curr = heap.top().endpoint;
      heap.pop();
    } while (visited[curr]);
    visited[curr] = true;
    parents[curr] = prev;
    for (auto& edge : edges_[curr]) {
      if (!visited[edge.endpoint] &&
          edge.weight + distances[curr] < distances[edge.endpoint]) {
        distances[edge.endpoint] = edge.weight + distances[curr];
        heap.push({curr, edge.endpoint, distances[edge.endpoint]});
      }
    }
  }
}
}  // namespace artn

### Prompt

Your task is to create a Cpp solution to the following problem:

You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, 0 ≤ m ≤ 105), where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form ai, bi and wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106), where ai, bi are edge endpoints and wi is the length of the edge.

It is possible that the graph has loops and multiple edges between pair of vertices.

Output

Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.

Examples

Input

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1


Output

1 4 3 5 

Input

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1


Output

1 4 3 5 

### Response

```cpp
#include <bits/stdc++.h>
namespace artn {
struct _GraphEdge {
  int origin;
  int endpoint;
  int weight;
};
class Graph {
 private:
  std::vector<std::forward_list<_GraphEdge>> edges_;

 public:
  Graph(int size);
  void add_edge(int s, int t, int w);
  inline int size() const;
  void djkistra(int source, int* distances, int* parents);
};
bool operator>(const _GraphEdge& x, const _GraphEdge& y);
}  // namespace artn
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int vertex_count, edge_count;
  std::cin >> vertex_count >> edge_count;
  artn::Graph G = artn::Graph(vertex_count);
  for (int i = 0; i < edge_count; i++) {
    int v1, v2, w;
    std::cin >> v1 >> v2 >> w;
    G.add_edge(v1 - 1, v2 - 1, w);
  }
  int D[G.size()], P[G.size()];
  G.djkistra(0, D, P);
  if (D[G.size() - 1] == INT_MAX) {
    std::cout << -1 << "\n";
    return 0;
  }
  int previous = G.size() - 1;
  std::vector<int> path(1, previous);
  do {
    previous = P[previous];
    path.push_back(previous);
  } while (previous != P[previous]);
  for (int i = static_cast<int>(path.size() - 1); i >= 0; i--)
    std::cout << (path[i] + 1) << " ";
  std::cout << "\n";
}
namespace artn {
bool operator>(const _GraphEdge& x, const _GraphEdge& y) {
  return x.weight > y.weight;
}
Graph::Graph(int size) : edges_(size) {}
void Graph::add_edge(int s, int t, int w) {
  edges_[s].push_front({s, t, w});
  edges_[t].push_front({t, s, w});
}
inline int Graph::size() const { return static_cast<int>(edges_.size()); }
void Graph::djkistra(int source, int* distances, int* parents) {
  bool visited[size()];
  std::priority_queue<_GraphEdge, std::vector<_GraphEdge>,
                      std::greater<_GraphEdge>>
      heap;
  for (int i = 0; i < size(); i++) {
    distances[i] = INT_MAX;
    visited[i] = false;
  }
  distances[source] = 0;
  parents[source] = source;
  heap.push({source, source, 0});
  for (int i = 0; i < size(); i++) {
    int prev, curr;
    do {
      if (heap.empty()) return;
      prev = heap.top().origin;
      curr = heap.top().endpoint;
      heap.pop();
    } while (visited[curr]);
    visited[curr] = true;
    parents[curr] = prev;
    for (auto& edge : edges_[curr]) {
      if (!visited[edge.endpoint] &&
          edge.weight + distances[curr] < distances[edge.endpoint]) {
        distances[edge.endpoint] = edge.weight + distances[curr];
        heap.push({curr, edge.endpoint, distances[edge.endpoint]});
      }
    }
  }
}
}  // namespace artn

```