#include <bits/stdc++.h>
using namespace std;
const int infi = 1e9;
const long long int infl = 1e18;
const int MOD = 1e9 + 7;
long long int log_2(long long int n) {
  return (n > 1ll) ? 1ll + log_2(n / 2) : 0ll;
}
inline void add(long long int &a, long long int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline void sub(long long int &a, long long int b) {
  a -= b;
  if (a < 0) a += MOD;
}
inline string IntToString(long long int a) {
  char x[100];
  sprintf(x, "%lld", a);
  string s = x;
  return s;
}
inline long long int StringToInt(string a) {
  char x[100];
  long long int res;
  strcpy(x, a.c_str());
  sscanf(x, "%lld", &res);
  return res;
}
inline string GetString(void) {
  char x[1000005];
  scanf("%s", x);
  string s = x;
  return s;
}
inline string uppercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); ++(i))
    if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}
inline string lowercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); ++(i))
    if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}
inline void OPEN(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
void showarr(long long int arr[], long long int n) {
  int i;
  for (i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
void showvec(vector<long long int> v) {
  int i;
  for (i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
}
int isPalindrome(string str) {
  int l = 0;
  int h = str.length() - 1;
  while (h > l) {
    if (str[l++] != str[h--]) {
      return 0;
    }
  }
  return 1;
}
void showvecpair(vector<pair<long long int, long long int> > v) {
  for (int i = 0; i < (int)v.size(); i++) {
    cout << v[i].first << " " << v[i].second << endl;
  }
}
bool sortbysec(const pair<long long int, long long int> &a,
               const pair<long long int, long long int> &b) {
  return (a.second < b.second);
}
void bin(unsigned n) {
  unsigned i;
  for (i = 1 << 31; i > 0; i = i / 2) (n & i) ? printf("1") : printf("0");
}
long long int cntset(long long int n) {
  bitset<64> b1(n);
  return b1.count();
}
long long int N = 8;
void solve() {
  long long int INF = 1e18;
  long long int v, w, k, l, a, b, n, m, i, j, max = INT_MIN, min = INT_MAX,
                                              ctr = -1, cnt = 0, x, cnt1 = 0;
  cin >> n >> m;
  vector<pair<long long int, long long int> > adj[n + 1];
  vector<long long int> parent(n + 1, -1);
  vector<long long int> dist(n + 1, INF);
  for (i = 1; i <= m; i++) {
    cin >> a;
    cin >> b;
    cin >> w;
    adj[a].push_back(make_pair(b, w));
    adj[b].push_back(make_pair(a, w));
  }
  parent[1] = -1;
  set<pair<long long int, long long int> > q;
  dist[1] = 0;
  for (i = 1; i <= n; i++) {
    q.insert({dist[i], i});
  }
  while (!q.empty()) {
    v = q.begin()->second;
    q.erase(q.begin());
    for (i = 0; i < adj[v].size(); i++) {
      if (dist[adj[v][i].first] > dist[v] + adj[v][i].second) {
        q.erase({dist[adj[v][i].first], adj[v][i].first});
        dist[adj[v][i].first] = dist[v] + adj[v][i].second;
        q.insert({dist[adj[v][i].first], adj[v][i].first});
        parent[adj[v][i].first] = v;
      }
    }
  }
  if (dist[n] == INF)
    cout << "-1" << endl;
  else {
    vector<long long int> path;
    for (i = n; i != -1; i = parent[i]) {
      path.push_back(i);
    }
    reverse(path.begin(), path.end());
    showvec(path);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, T;
  T = 1;
  for (i = 1; i <= T; i++) {
    solve();
  }
  return 0;
}

### Prompt

Develop a solution in Cpp 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 infi = 1e9;
const long long int infl = 1e18;
const int MOD = 1e9 + 7;
long long int log_2(long long int n) {
  return (n > 1ll) ? 1ll + log_2(n / 2) : 0ll;
}
inline void add(long long int &a, long long int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline void sub(long long int &a, long long int b) {
  a -= b;
  if (a < 0) a += MOD;
}
inline string IntToString(long long int a) {
  char x[100];
  sprintf(x, "%lld", a);
  string s = x;
  return s;
}
inline long long int StringToInt(string a) {
  char x[100];
  long long int res;
  strcpy(x, a.c_str());
  sscanf(x, "%lld", &res);
  return res;
}
inline string GetString(void) {
  char x[1000005];
  scanf("%s", x);
  string s = x;
  return s;
}
inline string uppercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); ++(i))
    if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}
inline string lowercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); ++(i))
    if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}
inline void OPEN(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
void showarr(long long int arr[], long long int n) {
  int i;
  for (i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
void showvec(vector<long long int> v) {
  int i;
  for (i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
}
int isPalindrome(string str) {
  int l = 0;
  int h = str.length() - 1;
  while (h > l) {
    if (str[l++] != str[h--]) {
      return 0;
    }
  }
  return 1;
}
void showvecpair(vector<pair<long long int, long long int> > v) {
  for (int i = 0; i < (int)v.size(); i++) {
    cout << v[i].first << " " << v[i].second << endl;
  }
}
bool sortbysec(const pair<long long int, long long int> &a,
               const pair<long long int, long long int> &b) {
  return (a.second < b.second);
}
void bin(unsigned n) {
  unsigned i;
  for (i = 1 << 31; i > 0; i = i / 2) (n & i) ? printf("1") : printf("0");
}
long long int cntset(long long int n) {
  bitset<64> b1(n);
  return b1.count();
}
long long int N = 8;
void solve() {
  long long int INF = 1e18;
  long long int v, w, k, l, a, b, n, m, i, j, max = INT_MIN, min = INT_MAX,
                                              ctr = -1, cnt = 0, x, cnt1 = 0;
  cin >> n >> m;
  vector<pair<long long int, long long int> > adj[n + 1];
  vector<long long int> parent(n + 1, -1);
  vector<long long int> dist(n + 1, INF);
  for (i = 1; i <= m; i++) {
    cin >> a;
    cin >> b;
    cin >> w;
    adj[a].push_back(make_pair(b, w));
    adj[b].push_back(make_pair(a, w));
  }
  parent[1] = -1;
  set<pair<long long int, long long int> > q;
  dist[1] = 0;
  for (i = 1; i <= n; i++) {
    q.insert({dist[i], i});
  }
  while (!q.empty()) {
    v = q.begin()->second;
    q.erase(q.begin());
    for (i = 0; i < adj[v].size(); i++) {
      if (dist[adj[v][i].first] > dist[v] + adj[v][i].second) {
        q.erase({dist[adj[v][i].first], adj[v][i].first});
        dist[adj[v][i].first] = dist[v] + adj[v][i].second;
        q.insert({dist[adj[v][i].first], adj[v][i].first});
        parent[adj[v][i].first] = v;
      }
    }
  }
  if (dist[n] == INF)
    cout << "-1" << endl;
  else {
    vector<long long int> path;
    for (i = n; i != -1; i = parent[i]) {
      path.push_back(i);
    }
    reverse(path.begin(), path.end());
    showvec(path);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, T;
  T = 1;
  for (i = 1; i <= T; i++) {
    solve();
  }
  return 0;
}

```