#include <bits/stdc++.h>
using namespace std;
long double dis(double x, double y, double x1, double y1) {
  return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}
double PI = 3.14159265;
double e = 2.718281828;
void EnGz() {
  ios::sync_with_stdio(0);
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
}
long long GCD_(long long a, long long b) { return b ? GCD_(b, a % b) : a; }
long long LCM_(long long a, long long b) { return (a * b) / GCD_(a, b); }
bool prime(long long x) {
  if (x == 2) return true;
  if (x < 2 || x % 2 == 0) return false;
  for (long long i = 3; i * i <= x; i += 2)
    if (x % i == 0) return false;
  return true;
}
void print(vector<int> v) {
  for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
  cout << endl;
}
long long int primeFactors(long long int n) {
  if (n % 2 == 0) return 2;
  for (long long int i = 3; i <= sqrt(n); i += 2)
    if (n % i == 0) return i;
  return n;
}
int n, m;
vector<vector<pair<int, long long>>> v;
vector<int> Parent;
vector<long long> dijkstra() {
  priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                 greater<pair<long long, int>>>
      q;
  vector<long long> Cost(n + 1);
  for (int i = 0; i <= n; i++) Cost[i] = 1e18;
  vector<bool> visited(n + 1);
  for (int i = 0; i <= n; i++) visited[i] = false;
  Cost[1] = 0;
  q.push(make_pair(0, 1));
  Parent[1] = -1;
  while (!q.empty()) {
    int current = q.top().second;
    q.pop();
    if (visited[current]) continue;
    visited[current] = true;
    for (int i = 0; i < v[current].size(); i++) {
      int child_node = v[current][i].first;
      if (!visited[child_node] &&
          Cost[child_node] > Cost[current] + v[current][i].second) {
        Cost[child_node] = Cost[current] + v[current][i].second;
        q.push(make_pair(Cost[child_node], child_node));
        Parent[child_node] = current;
      }
    }
  }
  return Cost;
}
int main() {
  EnGz();
  cin >> n >> m;
  v.resize(n + 1);
  Parent.resize(n + 1);
  for (int i = 0; i < m; i++) {
    int to, from;
    long long cost;
    cin >> to >> from >> cost;
    v[to].push_back(make_pair(from, cost));
    v[from].push_back(make_pair(to, cost));
  }
  vector<long long> Cost = dijkstra();
  if (Cost[n] == 1e18) return cout << -1, 0;
  stack<int> Path;
  Path.push(n);
  int cur = n;
  while (Parent[cur] != -1) {
    Path.push(Parent[cur]);
    cur = Path.top();
  }
  while (!Path.empty()) {
    cout << Path.top() << " ";
    Path.pop();
  }
  return 0;
}

### Prompt

Please formulate 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>
using namespace std;
long double dis(double x, double y, double x1, double y1) {
  return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}
double PI = 3.14159265;
double e = 2.718281828;
void EnGz() {
  ios::sync_with_stdio(0);
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
}
long long GCD_(long long a, long long b) { return b ? GCD_(b, a % b) : a; }
long long LCM_(long long a, long long b) { return (a * b) / GCD_(a, b); }
bool prime(long long x) {
  if (x == 2) return true;
  if (x < 2 || x % 2 == 0) return false;
  for (long long i = 3; i * i <= x; i += 2)
    if (x % i == 0) return false;
  return true;
}
void print(vector<int> v) {
  for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
  cout << endl;
}
long long int primeFactors(long long int n) {
  if (n % 2 == 0) return 2;
  for (long long int i = 3; i <= sqrt(n); i += 2)
    if (n % i == 0) return i;
  return n;
}
int n, m;
vector<vector<pair<int, long long>>> v;
vector<int> Parent;
vector<long long> dijkstra() {
  priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                 greater<pair<long long, int>>>
      q;
  vector<long long> Cost(n + 1);
  for (int i = 0; i <= n; i++) Cost[i] = 1e18;
  vector<bool> visited(n + 1);
  for (int i = 0; i <= n; i++) visited[i] = false;
  Cost[1] = 0;
  q.push(make_pair(0, 1));
  Parent[1] = -1;
  while (!q.empty()) {
    int current = q.top().second;
    q.pop();
    if (visited[current]) continue;
    visited[current] = true;
    for (int i = 0; i < v[current].size(); i++) {
      int child_node = v[current][i].first;
      if (!visited[child_node] &&
          Cost[child_node] > Cost[current] + v[current][i].second) {
        Cost[child_node] = Cost[current] + v[current][i].second;
        q.push(make_pair(Cost[child_node], child_node));
        Parent[child_node] = current;
      }
    }
  }
  return Cost;
}
int main() {
  EnGz();
  cin >> n >> m;
  v.resize(n + 1);
  Parent.resize(n + 1);
  for (int i = 0; i < m; i++) {
    int to, from;
    long long cost;
    cin >> to >> from >> cost;
    v[to].push_back(make_pair(from, cost));
    v[from].push_back(make_pair(to, cost));
  }
  vector<long long> Cost = dijkstra();
  if (Cost[n] == 1e18) return cout << -1, 0;
  stack<int> Path;
  Path.push(n);
  int cur = n;
  while (Parent[cur] != -1) {
    Path.push(Parent[cur]);
    cur = Path.top();
  }
  while (!Path.empty()) {
    cout << Path.top() << " ";
    Path.pop();
  }
  return 0;
}

```