#include <bits/stdc++.h>
template <typename heap_T>
class max_heap {
 private:
  bool allgood;
  int curle;
  int mxle;
  heap_T *heap;
  int *key_to_heap;
  int *heap_to_key;
  inline void push(int pos);
  inline void swap_hpos(int pos, int npos);
  inline void update_hpos(int pos, int npos);

 public:
  max_heap(int maxlength);
  ~max_heap();
  bool pop();
  int max_key();
  heap_T max_val();
  bool empty();
  bool push(int key, heap_T value);
  bool had_error();
};
template <typename heap_T>
max_heap<heap_T>::max_heap(int maxlength) {
  curle = 0;
  mxle = maxlength;
  heap = new heap_T[mxle];
  key_to_heap = new int[mxle];
  heap_to_key = new int[mxle];
  for (int i = 0; i < mxle; i++) {
    key_to_heap[i] = -1;
  }
  allgood = true;
}
template <typename heap_T>
max_heap<heap_T>::~max_heap() {
  delete[] heap;
  delete[] key_to_heap;
  delete[] heap_to_key;
}
template <typename heap_T>
inline void max_heap<heap_T>::swap_hpos(int pos, int npos) {
  heap_T hn = heap[pos];
  heap[pos] = heap[npos];
  heap[npos] = hn;
  int k1 = heap_to_key[pos], k2 = heap_to_key[npos];
  key_to_heap[k1] = npos;
  key_to_heap[k2] = pos;
  heap_to_key[pos] = k2;
  heap_to_key[npos] = k1;
}
template <typename heap_T>
inline void max_heap<heap_T>::update_hpos(int pos, int npos) {
  heap[pos] = heap[npos];
  int k = heap_to_key[npos];
  key_to_heap[k] = pos;
  heap_to_key[pos] = k;
}
template <typename heap_T>
bool max_heap<heap_T>::pop() {
  if (!allgood || curle <= 0) {
    allgood = false;
    return false;
  }
  int key = heap_to_key[0];
  int cpos = 0;
  while (2 * cpos + 2 < curle) {
    int leftp = 2 * cpos + 1;
    if (heap[leftp] < heap[leftp + 1]) {
      update_hpos(cpos, leftp + 1);
      cpos = leftp + 1;
    } else {
      update_hpos(cpos, leftp);
      cpos = leftp;
    }
  }
  int leftp = 2 * cpos + 1;
  if (leftp + 1 == curle) {
    update_hpos(cpos, leftp);
    cpos = leftp;
  }
  if (cpos != curle - 1) {
    update_hpos(cpos, curle - 1);
    push(cpos);
  }
  key_to_heap[key] = -1;
  curle--;
  return true;
}
template <typename heap_T>
inline void max_heap<heap_T>::push(int pos) {
  int npos = (pos - 1) / 2;
  while (pos != 0 && heap[npos] < heap[pos]) {
    swap_hpos(pos, npos);
    pos = npos;
    npos = (npos - 1) / 2;
  }
}
template <typename heap_T>
bool max_heap<heap_T>::push(int key, heap_T value) {
  if (curle >= mxle || !allgood) {
    allgood = false;
    return false;
  }
  int hpos = key_to_heap[key];
  if (hpos >= 0) {
    if (value <= heap[hpos]) {
      return false;
    } else {
      heap[hpos] = value;
      push(hpos);
    }
  } else {
    heap[curle] = value;
    key_to_heap[key] = curle;
    heap_to_key[curle] = key;
    push(curle);
    curle++;
  }
  return true;
}
template <typename heap_T>
bool max_heap<heap_T>::empty() {
  return (curle == 0);
}
template <typename heap_T>
int max_heap<heap_T>::max_key() {
  return heap_to_key[0];
}
template <typename heap_T>
heap_T max_heap<heap_T>::max_val() {
  return heap[0];
}
template <typename heap_T>
bool max_heap<heap_T>::had_error() {
  return allgood;
}
using namespace std;
struct e {
  int to;
  int w;
};
int main(int agrc, char *argv[]) {
  int n, m;
  scanf("%d %d", &n, &m);
  list<e> *vcor = new list<e>[n];
  for (int i = 0; i < m; i++) {
    int from;
    e ed;
    scanf("%d %d %d", &from, &ed.to, &ed.w);
    from--;
    ed.to--;
    vcor[from].push_back(ed);
    int to = ed.to;
    ed.to = from;
    vcor[to].push_back(ed);
  }
  max_heap<long long int> que(n);
  que.push(0, 0);
  long long int *best = new long long int[n];
  for (int i = 0; i < n; i++) best[i] = -1;
  list<e>::iterator it;
  while (!que.empty()) {
    long long int w = que.max_val();
    int vpos = que.max_key();
    best[vpos] = -w;
    que.pop();
    for (it = vcor[vpos].begin(); it != vcor[vpos].end(); it++) {
      long long int wcur = w - it->w;
      if (best[it->to] < 0) que.push(it->to, wcur);
    }
  }
  if (best[n - 1] < 0) {
    printf("-1");
  } else {
    int pos = n - 1;
    list<int> sol;
    while (pos != 0) {
      it = vcor[pos].begin();
      while (it != vcor[pos].end() && (it->w + best[it->to] != best[pos])) {
        it++;
      }
      sol.push_back(pos + 1);
      pos = it->to;
    }
    printf("1");
    while (!sol.empty()) {
      printf(" %d", sol.back());
      sol.pop_back();
    }
  }
  for (int i = 0; i < n; i++) vcor[i].clear();
  delete[] vcor;
  delete[] best;
  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>
template <typename heap_T>
class max_heap {
 private:
  bool allgood;
  int curle;
  int mxle;
  heap_T *heap;
  int *key_to_heap;
  int *heap_to_key;
  inline void push(int pos);
  inline void swap_hpos(int pos, int npos);
  inline void update_hpos(int pos, int npos);

 public:
  max_heap(int maxlength);
  ~max_heap();
  bool pop();
  int max_key();
  heap_T max_val();
  bool empty();
  bool push(int key, heap_T value);
  bool had_error();
};
template <typename heap_T>
max_heap<heap_T>::max_heap(int maxlength) {
  curle = 0;
  mxle = maxlength;
  heap = new heap_T[mxle];
  key_to_heap = new int[mxle];
  heap_to_key = new int[mxle];
  for (int i = 0; i < mxle; i++) {
    key_to_heap[i] = -1;
  }
  allgood = true;
}
template <typename heap_T>
max_heap<heap_T>::~max_heap() {
  delete[] heap;
  delete[] key_to_heap;
  delete[] heap_to_key;
}
template <typename heap_T>
inline void max_heap<heap_T>::swap_hpos(int pos, int npos) {
  heap_T hn = heap[pos];
  heap[pos] = heap[npos];
  heap[npos] = hn;
  int k1 = heap_to_key[pos], k2 = heap_to_key[npos];
  key_to_heap[k1] = npos;
  key_to_heap[k2] = pos;
  heap_to_key[pos] = k2;
  heap_to_key[npos] = k1;
}
template <typename heap_T>
inline void max_heap<heap_T>::update_hpos(int pos, int npos) {
  heap[pos] = heap[npos];
  int k = heap_to_key[npos];
  key_to_heap[k] = pos;
  heap_to_key[pos] = k;
}
template <typename heap_T>
bool max_heap<heap_T>::pop() {
  if (!allgood || curle <= 0) {
    allgood = false;
    return false;
  }
  int key = heap_to_key[0];
  int cpos = 0;
  while (2 * cpos + 2 < curle) {
    int leftp = 2 * cpos + 1;
    if (heap[leftp] < heap[leftp + 1]) {
      update_hpos(cpos, leftp + 1);
      cpos = leftp + 1;
    } else {
      update_hpos(cpos, leftp);
      cpos = leftp;
    }
  }
  int leftp = 2 * cpos + 1;
  if (leftp + 1 == curle) {
    update_hpos(cpos, leftp);
    cpos = leftp;
  }
  if (cpos != curle - 1) {
    update_hpos(cpos, curle - 1);
    push(cpos);
  }
  key_to_heap[key] = -1;
  curle--;
  return true;
}
template <typename heap_T>
inline void max_heap<heap_T>::push(int pos) {
  int npos = (pos - 1) / 2;
  while (pos != 0 && heap[npos] < heap[pos]) {
    swap_hpos(pos, npos);
    pos = npos;
    npos = (npos - 1) / 2;
  }
}
template <typename heap_T>
bool max_heap<heap_T>::push(int key, heap_T value) {
  if (curle >= mxle || !allgood) {
    allgood = false;
    return false;
  }
  int hpos = key_to_heap[key];
  if (hpos >= 0) {
    if (value <= heap[hpos]) {
      return false;
    } else {
      heap[hpos] = value;
      push(hpos);
    }
  } else {
    heap[curle] = value;
    key_to_heap[key] = curle;
    heap_to_key[curle] = key;
    push(curle);
    curle++;
  }
  return true;
}
template <typename heap_T>
bool max_heap<heap_T>::empty() {
  return (curle == 0);
}
template <typename heap_T>
int max_heap<heap_T>::max_key() {
  return heap_to_key[0];
}
template <typename heap_T>
heap_T max_heap<heap_T>::max_val() {
  return heap[0];
}
template <typename heap_T>
bool max_heap<heap_T>::had_error() {
  return allgood;
}
using namespace std;
struct e {
  int to;
  int w;
};
int main(int agrc, char *argv[]) {
  int n, m;
  scanf("%d %d", &n, &m);
  list<e> *vcor = new list<e>[n];
  for (int i = 0; i < m; i++) {
    int from;
    e ed;
    scanf("%d %d %d", &from, &ed.to, &ed.w);
    from--;
    ed.to--;
    vcor[from].push_back(ed);
    int to = ed.to;
    ed.to = from;
    vcor[to].push_back(ed);
  }
  max_heap<long long int> que(n);
  que.push(0, 0);
  long long int *best = new long long int[n];
  for (int i = 0; i < n; i++) best[i] = -1;
  list<e>::iterator it;
  while (!que.empty()) {
    long long int w = que.max_val();
    int vpos = que.max_key();
    best[vpos] = -w;
    que.pop();
    for (it = vcor[vpos].begin(); it != vcor[vpos].end(); it++) {
      long long int wcur = w - it->w;
      if (best[it->to] < 0) que.push(it->to, wcur);
    }
  }
  if (best[n - 1] < 0) {
    printf("-1");
  } else {
    int pos = n - 1;
    list<int> sol;
    while (pos != 0) {
      it = vcor[pos].begin();
      while (it != vcor[pos].end() && (it->w + best[it->to] != best[pos])) {
        it++;
      }
      sol.push_back(pos + 1);
      pos = it->to;
    }
    printf("1");
    while (!sol.empty()) {
      printf(" %d", sol.back());
      sol.pop_back();
    }
  }
  for (int i = 0; i < n; i++) vcor[i].clear();
  delete[] vcor;
  delete[] best;
  return 0;
}

```