#include <bits/stdc++.h>
using namespace std;
const int MAXN = 412345;
const int MAXINT = 2047483098;
const long long int MOD = 1e9 + 7;
const int MAX = 1e4;
const long double pi = 2 * acosl(0);
const long double EPS = 1e-10;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
bool isPrime(long long unsigned n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
int nCr(int n, int r) {
  int res = 1;
  if (n < r) return -1;
  r = min(r, n - r);
  for (long long unsigned int i = 0; i < r; i++) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
int nPr(int n, int r) {
  int res = 1;
  if (n < r) return -1;
  for (long long unsigned int i = 0; i < r; i++) res *= (n - i);
  return res;
}
void solve() {
  long long int n, m;
  cin >> n >> m;
  vector<long long int> xxx(n + 10, -1);
  long long int INF = 1e18;
  vector<pair<long long int, long long int> > v[n + 10];
  vector<long long int> dist(n + 10, INF);
  long long int a, b, c;
  for (long long unsigned int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
  }
  priority_queue<pair<long long int, long long int>,
                 vector<pair<long long int, long long int> >,
                 greater<pair<long long int, long long int> > >
      s;
  dist[1] = 0;
  s.push({0, 1});
  while (!s.empty()) {
    long long int vo = s.top().second;
    long long int d = s.top().first;
    s.pop();
    if (d != dist[vo]) {
      continue;
    }
    for (auto e : v[vo]) {
      long long int to = e.first;
      long long int le = e.second;
      if (le + dist[vo] < dist[to]) {
        dist[to] = le + dist[vo];
        s.push({dist[to], to});
        xxx[to] = vo;
      }
    }
  }
  if (dist[n] == INF) {
    cout << "-1";
  } else {
    long long int curr = n;
    vector<long long int> ans;
    while (curr != -1) {
      ans.push_back(curr);
      curr = xxx[curr];
    }
    reverse(ans.begin(), ans.end());
    for (auto x : ans) cout << x << " ";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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;
const int MAXN = 412345;
const int MAXINT = 2047483098;
const long long int MOD = 1e9 + 7;
const int MAX = 1e4;
const long double pi = 2 * acosl(0);
const long double EPS = 1e-10;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
bool isPrime(long long unsigned n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
int nCr(int n, int r) {
  int res = 1;
  if (n < r) return -1;
  r = min(r, n - r);
  for (long long unsigned int i = 0; i < r; i++) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
int nPr(int n, int r) {
  int res = 1;
  if (n < r) return -1;
  for (long long unsigned int i = 0; i < r; i++) res *= (n - i);
  return res;
}
void solve() {
  long long int n, m;
  cin >> n >> m;
  vector<long long int> xxx(n + 10, -1);
  long long int INF = 1e18;
  vector<pair<long long int, long long int> > v[n + 10];
  vector<long long int> dist(n + 10, INF);
  long long int a, b, c;
  for (long long unsigned int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
  }
  priority_queue<pair<long long int, long long int>,
                 vector<pair<long long int, long long int> >,
                 greater<pair<long long int, long long int> > >
      s;
  dist[1] = 0;
  s.push({0, 1});
  while (!s.empty()) {
    long long int vo = s.top().second;
    long long int d = s.top().first;
    s.pop();
    if (d != dist[vo]) {
      continue;
    }
    for (auto e : v[vo]) {
      long long int to = e.first;
      long long int le = e.second;
      if (le + dist[vo] < dist[to]) {
        dist[to] = le + dist[vo];
        s.push({dist[to], to});
        xxx[to] = vo;
      }
    }
  }
  if (dist[n] == INF) {
    cout << "-1";
  } else {
    long long int curr = n;
    vector<long long int> ans;
    while (curr != -1) {
      ans.push_back(curr);
      curr = xxx[curr];
    }
    reverse(ans.begin(), ans.end());
    for (auto x : ans) cout << x << " ";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}

```