#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int N = 100005;
set<char> vowel = {'A', 'O', 'Y', 'E', 'U', 'I', 'a', 'o', 'y', 'e', 'u', 'i'};
long long gcd(long long a, long long b) { return (b == 0 ? a : gcd(b, a % b)); }
long long lcm(long long a, long long b) { return a * (b / gcd(a, b)); }
bool issquare(long long w) { return trunc(sqrt(w)) * trunc(sqrt(w)) == w; }
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, 1, -1, -1};
long long n, m, k, a, l, r, b, t, ans = 0, res = 0, posmin, posmax, x, y, www,
                                  eee, w, e, z = 0, xmax = 0, ymax = 0;
vector<long long> v, vv;
double db;
vector<string> vs;
long long dist[N], parent[N];
vector<pair<long long, long long> > vvv, sss;
map<long long, vector<pair<long long, long long> > > adj;
char c;
bool check = true, vis[N];
map<long long, long long> maa;
map<char, long long> ma;
string ch, ch1, ch2;
vector<char> anss;
void dijkstra(long long src) {
  for (int i = 0; i < n; i++) {
    vis[i] = 0;
    dist[i] = 1e12;
    parent[i] = -1;
    sort(adj[i].begin(), adj[i].end());
  }
  priority_queue<pair<long long, long long> > pq;
  dist[0] = 0;
  pq.push(make_pair(0, src));
  while (!pq.empty()) {
    pair<long long, long long> ras = pq.top();
    pq.pop();
    if (vis[ras.second]) continue;
    vis[ras.second] = 1;
    for (auto t : adj[ras.second]) {
      if (vis[t.first]) continue;
      if (dist[t.first] > dist[ras.second] + t.second) {
        parent[t.first] = ras.second;
        dist[t.first] = dist[ras.second] + t.second;
        pq.push(make_pair(-dist[t.first], t.first));
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> x >> y >> z;
    x--;
    y--;
    if (x == y) continue;
    adj[x].push_back(make_pair(y, z));
    adj[y].push_back(make_pair(x, z));
  }
  dijkstra(0);
  if (dist[n - 1] >= 1e12) {
    cout << -1;
    return 0;
  }
  x = n - 1;
  v.push_back(x + 1);
  while (parent[x] != -1) {
    v.push_back(parent[x] + 1);
    x = parent[x];
  }
  for (int i = v.size() - 1; i >= 0; i--) {
    cout << v[i] << " ";
  }
  return 0;
}

### Prompt

Generate 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;
const int MOD = 1000000007;
const int N = 100005;
set<char> vowel = {'A', 'O', 'Y', 'E', 'U', 'I', 'a', 'o', 'y', 'e', 'u', 'i'};
long long gcd(long long a, long long b) { return (b == 0 ? a : gcd(b, a % b)); }
long long lcm(long long a, long long b) { return a * (b / gcd(a, b)); }
bool issquare(long long w) { return trunc(sqrt(w)) * trunc(sqrt(w)) == w; }
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, 1, -1, -1};
long long n, m, k, a, l, r, b, t, ans = 0, res = 0, posmin, posmax, x, y, www,
                                  eee, w, e, z = 0, xmax = 0, ymax = 0;
vector<long long> v, vv;
double db;
vector<string> vs;
long long dist[N], parent[N];
vector<pair<long long, long long> > vvv, sss;
map<long long, vector<pair<long long, long long> > > adj;
char c;
bool check = true, vis[N];
map<long long, long long> maa;
map<char, long long> ma;
string ch, ch1, ch2;
vector<char> anss;
void dijkstra(long long src) {
  for (int i = 0; i < n; i++) {
    vis[i] = 0;
    dist[i] = 1e12;
    parent[i] = -1;
    sort(adj[i].begin(), adj[i].end());
  }
  priority_queue<pair<long long, long long> > pq;
  dist[0] = 0;
  pq.push(make_pair(0, src));
  while (!pq.empty()) {
    pair<long long, long long> ras = pq.top();
    pq.pop();
    if (vis[ras.second]) continue;
    vis[ras.second] = 1;
    for (auto t : adj[ras.second]) {
      if (vis[t.first]) continue;
      if (dist[t.first] > dist[ras.second] + t.second) {
        parent[t.first] = ras.second;
        dist[t.first] = dist[ras.second] + t.second;
        pq.push(make_pair(-dist[t.first], t.first));
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> x >> y >> z;
    x--;
    y--;
    if (x == y) continue;
    adj[x].push_back(make_pair(y, z));
    adj[y].push_back(make_pair(x, z));
  }
  dijkstra(0);
  if (dist[n - 1] >= 1e12) {
    cout << -1;
    return 0;
  }
  x = n - 1;
  v.push_back(x + 1);
  while (parent[x] != -1) {
    v.push_back(parent[x] + 1);
    x = parent[x];
  }
  for (int i = v.size() - 1; i >= 0; i--) {
    cout << v[i] << " ";
  }
  return 0;
}

```