#include <bits/stdc++.h>
using namespace std;
void _print(long long t) { cerr << t; }
void _print(unsigned t) { cerr << t; }
void _print(unsigned long t) { cerr << t; }
void _print(unsigned long long t) { cerr << t; }
void _print(float t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(long double t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(const char *t) { cerr << t; }
void _print(const string &t) { cerr << t; }
void _print(bool t) { cerr << (t ? "true" : "false"); }
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
const long long INF = (long long)1e18;
const long long MOD = (long long)1e9 + 7;
const long long N = (long long)1e5 + 7;
vector<pair<long long, long long>> adj[N];
long long vis[N], parent[N], dis[N];
void init() {}
void solve() {
  long long n, m;
  cin >> n >> m;
  for (long long i = 0; i <= n; i++) {
    dis[i] = INF;
    vis[i] = 0;
  }
  for (long long j = 0; j < m; j++) {
    long long u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      pq;
  vis[1] = 0;
  dis[1] = 1;
  parent[1] = -1;
  pq.push({0, 1});
  while (!pq.empty()) {
    long long x = pq.top().second;
    pq.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (pair<long long, long long> i : adj[x]) {
      if (dis[x] + i.second < dis[i.first]) {
        dis[i.first] = dis[x] + i.second;
        parent[i.first] = x;
        pq.push({dis[i.first], i.first});
      }
    }
  }
  if (dis[n] == INF) {
    cout << -1 << endl;
    return;
  }
  vector<long long> ans;
  long long cur = n;
  while (cur != -1) {
    ans.push_back(cur);
    cur = parent[cur];
  }
  for (long long i = ans.size() - 1; i >= 0; i--) {
    cout << ans[i] << " ";
  }
  cout << endl;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  init();
  long long 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;
void _print(long long t) { cerr << t; }
void _print(unsigned t) { cerr << t; }
void _print(unsigned long t) { cerr << t; }
void _print(unsigned long long t) { cerr << t; }
void _print(float t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(long double t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(const char *t) { cerr << t; }
void _print(const string &t) { cerr << t; }
void _print(bool t) { cerr << (t ? "true" : "false"); }
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
const long long INF = (long long)1e18;
const long long MOD = (long long)1e9 + 7;
const long long N = (long long)1e5 + 7;
vector<pair<long long, long long>> adj[N];
long long vis[N], parent[N], dis[N];
void init() {}
void solve() {
  long long n, m;
  cin >> n >> m;
  for (long long i = 0; i <= n; i++) {
    dis[i] = INF;
    vis[i] = 0;
  }
  for (long long j = 0; j < m; j++) {
    long long u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      pq;
  vis[1] = 0;
  dis[1] = 1;
  parent[1] = -1;
  pq.push({0, 1});
  while (!pq.empty()) {
    long long x = pq.top().second;
    pq.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (pair<long long, long long> i : adj[x]) {
      if (dis[x] + i.second < dis[i.first]) {
        dis[i.first] = dis[x] + i.second;
        parent[i.first] = x;
        pq.push({dis[i.first], i.first});
      }
    }
  }
  if (dis[n] == INF) {
    cout << -1 << endl;
    return;
  }
  vector<long long> ans;
  long long cur = n;
  while (cur != -1) {
    ans.push_back(cur);
    cur = parent[cur];
  }
  for (long long i = ans.size() - 1; i >= 0; i--) {
    cout << ans[i] << " ";
  }
  cout << endl;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  init();
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

```