## Algorithm

C. Dijkstra?
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

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 aibi 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
Copy
`5 61 2 22 5 52 3 41 4 14 3 33 5 1`
output
Copy
`1 4 3 5 `
input
Copy
`5 61 2 22 5 52 3 41 4 14 3 33 5 1`
output
Copy
`1 4 3 5 `

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <stack>

int main(){

int64_t n, m; scanf("%lld %lld\n", &n, &m);
std::vector<std::vector<std::pair<int64_t, int64_t> > > g(n + 1);
while(m--){
int64_t u, v, w; scanf("%lld %lld %lld", &u, &v, &w);
g[u].push_back(std::pair < int64_t, int64_t>(v, w));
g[v].push_back(std::pair<int64_t, int64_t>(u, w));
}

int64_t source(1), target(n);
std::set<std::pair<int64_t, int64_t> > q;
q.insert(std::pair<int64_t, int64_t>(0, source));
std::vector<int64_t> dist(n + 1, -1);
std::vector<int64_t> from(n + 1, -1); from[0] = 0; from[1] = 1;
std::vector<bool> visited(n + 1, 0);
while(!q.empty()){
std::pair<int64_t, int64_t> cur = *q.begin();
q.erase(q.begin());
int64_t distance = cur.first;
int64_t vertex = cur.second;
if(visited[vertex]){continue;}
visited[vertex] = true;
for(int64_t p = 0; p < g[vertex].size(); p++){
std::pair<int64_t, int64_t> edge = g[vertex][p];
int64_t u = edge.first;
int64_t w = edge.second;
if(visited[u]){continue;}
if(dist[u] < 0 || dist[u] > distance + w){
dist[u] = distance + w;
q.insert(std::pair<int64_t, int64_t>(dist[u], u));
from[u] = vertex;
}
}
}

if(dist[n] < 0){puts("-1");}
else{
std::stack<int64_t> st; st.push(n);
do{st.push(from[st.top()]);} while(st.top() != from[st.top()]);
while(!st.empty()){printf("%lld ", st.top()); st.pop();}
puts("");
}

return 0;
}``````
Copy The Code &

Input

cmd
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

Output

cmd
1 4 3 5