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

Difficulty: HARD
Tags: Graph algorithms

Shortest paths

Starter code:

Solutions:
from collections import defaultdict
from heapq import heappush, heapify, heappop
INF = 10 ** 18

class Graph:

	def __init__(self):
		self.adj_list = defaultdict(list)

	def add_edge(self, src, dest, cost):
		self.adj_list[src].append((dest, cost))
		self.adj_list[dest].append((src, cost))

def dijkstra(graph, src, dest, n):
	dist = [INF] * n
	vis = [False] * n
	dist[src] = 0
	min_queue = [(0, src)]
	heapify(min_queue)
	parent = [-1] * n
	while min_queue:
		(d, u) = heappop(min_queue)
		if vis[u]:
			continue
		vis[u] = True
		for (v, d2) in graph.adj_list[u]:
			if d2 + d < dist[v]:
				dist[v] = d2 + d
				heappush(min_queue, (dist[v], v))
				parent[v] = u
	if dist[dest] == INF:
		return '-1'
	path = []
	curr = dest
	while curr != -1:
		path.append(curr + 1)
		curr = parent[curr]
	path.reverse()
	return ' '.join((str(i) for i in path))

def main():
	graph = Graph()
	(n, m) = [int(i) for i in input().split()]
	for i in range(m):
		(u, v, w) = [int(j) for j in input().split()]
		u -= 1
		v -= 1
		graph.add_edge(u, v, w)
	print(dijkstra(graph, 0, n - 1, n))
main()


from heapq import *
(n, m) = map(int, input().split())
adjacency_list = [[]]
distanceToRoot = [float('inf')]
predecessor = [None]
for i in range(1, n + 1):
	adjacency_list.append([])
	distanceToRoot.append(float('inf'))
	predecessor.append(None)
for i in range(m):
	(a, b, w) = map(int, input().split())
	adjacency_list[a].append((b, w))
	adjacency_list[b].append((a, w))
min_heap = []
distanceToRoot[1] = 0
heappush(min_heap, (0, 1))
while min_heap:
	(distanceToRootFromU, uid) = heappop(min_heap)
	for (vid, weight) in adjacency_list[uid]:
		distanceThroughU = distanceToRootFromU + weight
		if distanceToRoot[vid] > distanceThroughU:
			distanceToRoot[vid] = distanceThroughU
			predecessor[vid] = uid
			heappush(min_heap, (distanceThroughU, vid))
nod = n
output_list = []
while nod != 1 and nod != None:
	output_list += [nod]
	nod = predecessor[nod]
if nod != None:
	output_list += [nod]
	output_list.reverse()
	print(' '.join(map(str, output_list)))
else:
	print('-1')


from math import inf
import heapq

def dijkstra(grafo, raiz):
	N = len(grafo)
	dist = [inf] * N
	prev = [None] * N
	visitados = [False] * N
	dist[raiz] = 0
	Q = [(0, raiz)]
	while Q:
		(_, no) = heapq.heappop(Q)
		if not visitados[no]:
			visitados[no] = True
			for nex in grafo[no]:
				if dist[no] + grafo[no][nex] < dist[nex]:
					dist[nex] = dist[no] + grafo[no][nex]
					heapq.heappush(Q, (dist[nex], nex))
					prev[nex] = no
	return (dist, prev)
(n, m) = [int(x) for x in input().split()]
grafo = dict(((i, {}) for i in range(n + 1)))
for _ in range(m):
	(a, b, w) = [int(x) for x in input().split()]
	grafo[a][b] = w
	grafo[b][a] = w
(distancias, pred) = dijkstra(grafo, 1)
if distancias[n] == inf:
	print(-1)
else:
	caminho = []
	prev = n
	while prev is not None:
		caminho.append(prev)
		prev = pred[prev]
	print(' '.join([str(caminho[len(caminho) - x - 1]) for x in range(len(caminho))]))


import math
import heapq

def dijkstra(a, b):
	distancias[a] = 0
	heapq.heappush(heap, (0, a))
	while len(heap) > 0:
		(to, vo) = heapq.heappop(heap)
		if vo == b:
			return True
		if visitados.get(vo) == None:
			visitados[vo] = True
			for aresta in grafo[vo]:
				dd = aresta.d
				td = aresta.tamanho
				if distancias[vo] + td < distancias[dd]:
					distancias[dd] = distancias[vo] + td
					heapq.heappush(heap, (distancias[dd], dd))
					predecessor[dd] = vo
	return False

class Aresta(object):

	def __init__(self, d, tamanho):
		super().__init__()
		self.d = d
		self.tamanho = tamanho

def getTamanho(aresta):
	return aresta.tamanho
(n, m) = map(int, input().split())
distancias = [math.inf] * (n + 1)
grafo = [[] for i in range(n + 1)]
heap = []
predecessor = [-1] * (n + 1)
visitados = {}
for i in range(m):
	(o, d, t) = map(int, input().split())
	grafo[o].append(Aresta(d, t))
	grafo[d].append(Aresta(o, t))
result = dijkstra(1, n)
if result == False:
	print('-1')
else:
	caminho = []
	i = n
	while i != -1:
		caminho.append(i)
		i = predecessor[i]
	caminho.reverse()
	print(*caminho)


from heapq import heappop, heappush
(N, inf) = (10 ** 5 + 10, 10 ** 18)
(n, m) = map(int, input().split())
(adj, visited, dist, parent) = ([[] for _ in range(N)], [False] * N, [inf] * N, [-1] * N)

def dijkstra(src):
	(pq, dist[src], parent[src]) = ([], 0, 0)
	heappush(pq, (0, src))
	while pq:
		(curr_dist, u) = heappop(pq)
		if visited[u]:
			continue
		visited[u] = True
		for (v, w) in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				parent[v] = u
				heappush(pq, (dist[v], v))
for _ in range(m):
	(u, v, w) = map(int, input().split())
	adj[u].append((v, w))
	adj[v].append((u, w))
dijkstra(1)
if dist[n] >= inf:
	print(-1)
	exit()
(stk, node) = ([], n)
while node:
	stk.append(node)
	node = parent[node]
for node in reversed(stk):
	print(node, end=' ')


from sys import stdin
from heapq import heappush, heappop

def dijkstra(graph):
	n = len(graph)
	INF = int(1e+18)
	dist = [INF] * n
	pre = [-1] * n
	heap = [(0, 0)]
	dist[0] = 0
	while len(heap) > 0:
		(d, u) = heappop(heap)
		if d > dist[u]:
			continue
		for edge in graph[u]:
			(v, w) = (edge[0], dist[u] + edge[1])
			if w < dist[v]:
				(dist[v], pre[v]) = (w, u)
				heappush(heap, (dist[v], v))
	if pre[n - 1] == -1:
		return False
	i = n - 1
	ans = []
	while i != -1:
		ans.append(i + 1)
		i = pre[i]
	ans.reverse()
	print(*ans)
	return True
(n, m) = [int(tmp) for tmp in stdin.readline().split()]
g = [[] for _ in range(n)]
for line in stdin.readlines():
	(a, b, w) = [int(tmp) for tmp in line.split()]
	g[a - 1].append([b - 1, w])
	g[b - 1].append([a - 1, w])
if not dijkstra(g):
	print(-1)


from heapq import heappop, heappush
from sys import stdin

def make_graph(m):
	graph = {}
	for i in range(m):
		s = input()
		(u, v, w) = (int(t) for t in s.split())
		if u not in graph:
			graph[u] = {}
		if v not in graph:
			graph[v] = {}
		graph[u][v] = w
		graph[v][u] = w
	return graph

class vertex_distance_type:

	@staticmethod
	def init_distance():
		vertex_distance_type.distance = {}

	def __init__(self, vertex):
		self.vertex = vertex

	def __lt__(self, rhs):
		return vertex_distance_type.distance[self.vertex] < vertex_distance_type.distance[rhs.vertex]

def find_path(graph, begin_vertex, end_vertex):
	vertex_distance_type.init_distance()
	queue = []
	predecessor = {end_vertex: end_vertex}
	vertex_distance_type.distance[end_vertex] = 0
	heappush(queue, vertex_distance_type(end_vertex))
	while queue:
		from_vertex = heappop(queue).vertex
		if from_vertex == begin_vertex:
			path = [begin_vertex]
			while from_vertex != end_vertex:
				from_vertex = predecessor[from_vertex]
				path.append(from_vertex)
			return path
		if from_vertex in graph:
			for to_vertex in graph[from_vertex]:
				distance = vertex_distance_type.distance[from_vertex] + graph[from_vertex][to_vertex]
				if to_vertex not in vertex_distance_type.distance or distance < vertex_distance_type.distance[to_vertex]:
					predecessor[to_vertex] = from_vertex
					vertex_distance_type.distance[to_vertex] = distance
					heappush(queue, vertex_distance_type(to_vertex))
	return [-1]

def test_case(n, m):
	begin_vertex = 1
	end_vertex = n
	graph = make_graph(m)
	path = find_path(graph, begin_vertex, end_vertex)
	print(' '.join((str(v) for v in path)))

def main():
	for s in stdin:
		(n, m) = (int(t) for t in s.split())
		test_case(n, m)
main()


from heapq import heappop, heappush
from collections import defaultdict

def dijkstra(g, s, f):
	h = [(0, s, s)]
	(visited, prev, dist) = (set(), {}, float('inf'))
	while len(h) > 0:
		(d, v, p) = heappop(h)
		if v not in visited:
			visited.add(v)
			prev[v] = p
			if v == f:
				dist = d
				break
			for (adj, adj_d) in g[v]:
				heappush(h, (adj_d + d, adj, v))
	(path, p) = ([], f)
	while p in prev and prev[p] != p:
		path.append(p)
		p = prev[p]
	path.append(s)
	return (path[::-1], dist)
(n, m) = map(int, input().split())
g = defaultdict(list)
for _ in range(m):
	(a, b, w) = map(int, input().split())
	g[a].append((b, w))
	g[b].append((a, w))
(p, d) = dijkstra(g, 1, n)
if n in p:
	print(' '.join(map(str, p)))
else:
	print('-1')


import sys
from heapq import heappush, heappop, heapify

def dijkstra(g, start, end):
	distances = dict.fromkeys(g, float('inf'))
	parents = dict.fromkeys(g)
	distances[start] = 0
	pending = [(0, start)]
	positions = {}
	while pending:
		(_, current) = heappop(pending)
		if current == end:
			break
		for (v, weight) in g[current]:
			if distances[current] + weight < distances[v]:
				parents[v] = current
				distances[v] = distances[current] + weight
				heappush(pending, (distances[v], v))
	else:
		return None
	path = []
	v = end
	while v is not None:
		path.append(v)
		v = parents[v]
	return path[::-1]
(n, m) = map(int, input().split())
g = {k: [] for k in range(1, n + 1)}
for _ in range(m):
	(tail, head, weight) = map(int, input().split())
	g[tail].append((head, weight))
	g[head].append((tail, weight))
result = dijkstra(g, 1, n)
if not result:
	print(-1)
else:
	print(' '.join([str(v) for v in result]))


from heapq import *
grafo = []
parents = []
costes = []
(nf, m) = [int(x) for x in input().split()]
for i in range(nf + 1):
	grafo.append([])
	parents.append(0)
	costes.append(10 ** 17)
for i in range(m):
	(g1, g2, cost) = [int(x) for x in input().split()]
	grafo[g1].append([cost, g2])
	grafo[g2].append([cost, g1])
h = []
visitados = set()
heappush(h, [0, 1, 0])
costes[1] = 0
costes[0] = 0
while h != []:
	minimo = heappop(h)
	(costo, n, np) = minimo
	visitados.add(n)
	for i in grafo[n]:
		(c, n2) = (i[0], i[1])
		if n2 not in visitados and costes[n2] > costes[n] + c:
			costes[n2] = costes[n] + c
			heappush(h, [costes[n2], n2, n])
			parents[n2] = n
if nf not in visitados:
	print(-1)
else:
	lista = []
	p = nf
	while p != 1:
		lista.append(str(p))
		p = parents[p]
	lista.append('1')
	print(' '.join(lista[::-1]))


import heapq

def dijkstra(start, max_val, adjacency_list):
	distance = [(max_val, -1)] * len(adjacency_list)
	visited = [False] * len(adjacency_list)
	queue = [(0, start, -1)]
	while len(queue) > 0:
		(d, n, f) = heapq.heappop(queue)
		if not visited[n]:
			visited[n] = True
			distance[n] = (d, f)
			for (m, w) in adjacency_list[n]:
				if not visited[m]:
					heapq.heappush(queue, (d + w, m, n))
	return distance

def main():
	max_val = float('Inf')
	(v, e) = map(int, input().split())
	adjacency_list = [[] for _ in range(v)]
	for _ in range(e):
		(a, b, w) = map(int, input().split())
		a -= 1
		b -= 1
		adjacency_list[a].append((b, w))
		adjacency_list[b].append((a, w))
	distance = dijkstra(0, max_val, adjacency_list)
	curr = distance[v - 1]
	visits = [v]
	while curr[0] != 0:
		if curr[0] == max_val:
			print(-1)
			return
		visits.append(curr[1] + 1)
		curr = distance[curr[1]]
	print(' '.join(map(str, reversed(visits))))
main()


import heapq

def dijkstra(start, maxval, adj):
	queue = [(0, start, -1)]
	dist = [(maxval, -1)] * len(adj)
	visited = [False] * len(adj)
	while len(queue) > 0:
		(d, n, f) = heapq.heappop(queue)
		if not visited[n]:
			visited[n] = True
			dist[n] = (d, f)
			for (m, w) in adj[n]:
				if not visited[m]:
					heapq.heappush(queue, (d + w, m, n))
	return dist
maxval = float('Inf')
(v, e) = map(int, input().split())
adj = [[] for _ in range(v)]
for _ in range(e):
	(a, b, w) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append((b, w))
	adj[b].append((a, w))
dist = dijkstra(0, maxval, adj)
current = dist[v - 1]
visits = [v]
while current[0] != 0:
	if current[0] == maxval:
		print(-1)
		exit()
	visits.append(current[1] + 1)
	current = dist[current[1]]
print(' '.join(map(str, reversed(visits))))


from __future__ import division, print_function
import os
import sys
from heapq import heappop, heappush
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def dijkstra(graph, start=0):
	n = len(graph)
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0.0
	queue = [(0.0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)

def main():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n)]
	for i in range(m):
		(_a, _b, _w) = input().split()
		(a, b, w) = (int(_a) - 1, int(_b) - 1, float(_w))
		graph[a].append((b, w))
		graph[b].append((a, w))
	(_, parents) = dijkstra(graph)
	if parents[n - 1] == -1:
		print(-1)
	else:
		(res, parent) = ([], n - 1)
		while parent != parents[0]:
			res.append(parent + 1)
			parent = parents[parent]
		res.reverse()
		print(*res)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from heapq import heappush, heappop
from collections import defaultdict

def dijkstra(src, graph, mdest, n):
	if src == mdest:
		return [1]
	dis = [float('inf')] * n
	pq = [(0, src, src)]
	parent = [-1] * n
	while pq:
		(d, src, dest) = heappop(pq)
		if dest == mdest:
			if dis[dest] > d:
				dis[dest] = d
			parent[dest] = src
			break
		if dis[dest] > d:
			dis[dest] = d
			parent[dest] = src
			for (ndest, nweigh) in graph[dest]:
				if ndest != dest:
					heappush(pq, (d + nweigh, dest, ndest))
	if dis[n - 1] == float('inf'):
		return [-1]
	res = []
	temp = parent[-1]
	res.append(n)
	while temp != 0:
		res.append(temp + 1)
		temp = parent[temp]
	res.append(1)
	return res[::-1]
(n, m) = map(int, input().split())
g = defaultdict(lambda : [])
for _ in range(m):
	(a, b, w) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append((b, w))
	g[b].append((a, w))
print(*dijkstra(0, g, n - 1, n))


import heapq
(vertices, edges) = [int(x) for x in input().strip().split()]
nodeDict = {}
for y in range(vertices + 1):
	nodeDict[y] = {}
for x in range(edges):
	(a, b, w) = [int(x) for x in input().strip().split()]
	if a not in nodeDict[b] or nodeDict[b][a] > w:
		nodeDict[b][a] = w
	if b not in nodeDict[a] or nodeDict[a][b] > w:
		nodeDict[a][b] = w
INF = float('inf')
queue = []
heapq.heappush(queue, (0, vertices))
previous = [-1] * (vertices + 1)
distance = [INF] * (vertices + 1)
visited = [False] * (vertices + 1)
distance[vertices] = 0
while len(queue) > 0:
	(d, vertex) = heapq.heappop(queue)
	if visited[vertex]:
		continue
	visited[vertex] = True
	if vertex == 1:
		break
	for endVertex in nodeDict[vertex]:
		alt = distance[vertex] + nodeDict[vertex][endVertex]
		if alt < distance[endVertex]:
			distance[endVertex] = alt
			previous[endVertex] = vertex
			heapq.heappush(queue, (alt, endVertex))
p = 1
path = []
while p != -1:
	path.append(str(p))
	p = previous[p]
if path[-1] != str(vertices):
	print(-1)
else:
	print(' '.join(path))


from collections import defaultdict, deque, Counter, OrderedDict
from heapq import heappop, heappush

def main():
	(n, m) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b, c) = map(int, input().split())
		adj[a].append((b, c))
		adj[b].append((a, c))
	(Q, dist, parent) = ([(0, 1)], [10 ** 13] * (n + 1), [0] * (n + 1))
	visited = parent[:]
	dist[1] = 0
	while Q:
		(d, v) = heappop(Q)
		if visited[v]:
			continue
		for (u, w) in adj[v]:
			w += d
			if not visited[u] and dist[u] > w:
				dist[u] = w
				parent[u] = v
				heappush(Q, (w, u))
		visited[v] = 1
	if not parent[n]:
		print('-1')
	else:
		(res, v) = ([], n)
		while v != 0:
			res.append(v)
			v = parent[v]
		print(' '.join(map(str, reversed(res))))
main()


from heapq import heappop, heappush

def dijkstra(adj, start):
	n = len(adj)
	dist = [-1] * n
	pred = [-1] * n
	heap = []
	dist[start] = 0
	heappush(heap, (0, start))
	while heap:
		(cur_dist, cur_v) = heappop(heap)
		if cur_dist != dist[cur_v]:
			continue
		for (next_v, next_w) in adj[cur_v]:
			if dist[next_v] == -1 or next_w + cur_dist < dist[next_v]:
				pred[next_v] = cur_v
				dist[next_v] = next_w + cur_dist
				heappush(heap, (dist[next_v], next_v))
	return (dist, pred)

def get_path(pred, end):
	if pred[end] == -1:
		return []
	out = [end]
	while pred[end] != -1:
		out.append(pred[end])
		end = pred[end]
	out.reverse()
	return out
(n, m) = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	(a, b, w) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append((b, w))
	adj[b].append((a, w))
(dist, pred) = dijkstra(adj, 0)
path = get_path(pred, n - 1)
if path:
	print(*[x + 1 for x in path])
else:
	print(-1)


from sys import stdin, stdout
from collections import deque
from heapq import heappush, heappop
a = list(map(int, stdin.readline().split()))
m = a[0]
pq = []
dist = [10 ** 12] * m
visited = [False] * m
graf = [[] for i in range(m)]
suly = []
start = 0
dist[start] = 0
prev = [0] * m
prev[start] = -1
mo = []
ready = 0
for x in range(a[1]):
	elem = list(map(int, stdin.readline().split()))
	elem[0] -= 1
	elem[1] -= 1
	graf[elem[0]].append((elem[1], elem[2]))
	graf[elem[1]].append((elem[0], elem[2]))
heappush(pq, (0, start))
while len(pq) > 0:
	(d, p) = heappop(pq)
	if visited[p] == True:
		continue
	visited[p] = True
	for i in range(len(graf[p])):
		v = graf[p][i][0]
		s = graf[p][i][1]
		if dist[v] > dist[p] + s:
			dist[v] = dist[p] + s
			prev[v] = p
			heappush(pq, (dist[v], v))
x = a[0] - 1
while x != -1:
	mo.append(x)
	x = prev[x]
if visited[m - 1] == False:
	ready = -1
for x in range(len(mo) - 1, -1, -1):
	if ready == 0:
		print(mo[x] + 1, end=' ')
	else:
		print(-1)
		break


from collections import defaultdict
import heapq
import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
I = 1 << 60
(n, m) = get_ints()
graph = defaultdict(list)
for _ in range(m):
	(a, b, w) = get_ints()
	graph[a - 1].append((w, b - 1))
	graph[b - 1].append((w, a - 1))
dist = [0] + [I] * n
path = [-1] * n
minheap = [(0, 0)]
while minheap:
	u = heapq.heappop(minheap)[1]
	for node in graph[u]:
		(temp, data) = (dist[u] + node[0], node[1])
		if temp < dist[data]:
			(dist[data], path[data]) = (temp, u)
			heapq.heappush(minheap, (dist[data], data))
if dist[n - 1] == I:
	print(-1)
else:
	(x, y) = (n - 1, [])
	while x != -1:
		y += [x + 1]
		x = path[x]
	y.reverse()
	print(' '.join(map(str, y)))


import heapq
from collections import defaultdict

def distances(graph, start, leng):
	d = {vertex: float('infinity') for vertex in range(1, leng + 1)}
	prev = {vertex: 1 for vertex in graph}
	d[start] = 0
	pq = [(0, start)]
	while len(pq) > 0:
		(dis, ver) = heapq.heappop(pq)
		if dis > d[ver]:
			continue
		for (nei, weight) in graph[ver].items():
			alt = dis + weight
			if alt < d[nei]:
				d[nei] = alt
				heapq.heappush(pq, (alt, nei))
				prev[nei] = ver
	return (prev, d)

def backtrace(parent, start, end):
	path = [end]
	while path[-1] != start:
		path.append(parent[path[-1]])
	path.reverse()
	return path
g = defaultdict(dict)
(n, m) = map(int, input().split())
for i in range(m):
	(u, v, w) = map(int, input().split())
	g[u][v] = w
	g[v][u] = w
(prev, d) = distances(g, 1, n)
if d[n] == float('infinity'):
	print(-1)
else:
	print(' '.join((str(i) for i in backtrace(prev, 1, n))))


from sys import stdin
from heapq import heappush, heappop

def trace(pre, dest):
	path = []
	while dest != -1:
		path.append(dest)
		dest = pre[dest]
	path.reverse()
	for v in path:
		print(v + 1, end=' ')

def dijkstra(graph):
	n = len(graph)
	INF = int(1e+18)
	dist = [INF] * n
	pre = [-1] * n
	heap = [(0, 0)]
	dist[0] = 0
	while len(heap) > 0:
		(d, u) = heappop(heap)
		if d > dist[u]:
			continue
		for edge in graph[u]:
			(v, w) = (edge[0], dist[u] + edge[1])
			if w < dist[v]:
				(dist[v], pre[v]) = (w, u)
				heappush(heap, (dist[v], v))
	if pre[n - 1] == -1:
		return False
	trace(pre, n - 1)
	return True

def main():
	(n, m) = [int(tmp) for tmp in stdin.readline().split()]
	g = [[] for _ in range(n)]
	for line in stdin.readlines():
		(u, v, c) = [int(tmp) for tmp in line.split()]
		g[u - 1].append((v - 1, c))
		g[v - 1].append((u - 1, c))
	if not dijkstra(g):
		print(-1)
main()


import heapq as hp

def search(target, queue, graph):
	global visited
	while len(visited) != target and len(queue):
		v = hp.heappop(queue)
		visited.add(v[2])
		d = v[0]
		for n in graph[v[2]]:
			if n[1] not in visited:
				if d + n[0] < path[n[1] - 1][0]:
					path[n[1] - 1] = (d + n[0], v[2], n[1])
					hp.heappush(queue, path[n[1] - 1])
		if v[2] == target:
			return
(nodes, m) = map(int, input().split())
(visited, g) = (set(), {})
path = [(1000000000000, 0, 0)] * nodes
q = [(0, 1, 1)]
hp.heapify(q)
for _ in range(m):
	(a, b, c) = map(int, input().split())
	if a not in g:
		g.update({a: [(c, b)]})
	else:
		g[a].append((c, b))
	if b not in g:
		g.update({b: [(c, a)]})
	else:
		g[b].append((c, a))
if nodes in g:
	search(nodes, q, g)
	if path[nodes - 1][2] == 0:
		print(-1)
		exit()
	ans = [nodes]
	while nodes != 1:
		nodes = path[nodes - 1][1]
		ans.append(nodes)
	ans.reverse()
	print(*ans)
else:
	print(-1)


from heapq import heappop, heappush
from sys import stdin

def graph(ne):
	g = {}
	for i in range(ne):
		s = input()
		(u, v, w) = (int(t) for t in s.split())
		if u not in g:
			g[u] = {}
		if v not in g:
			g[v] = {}
		if v not in g[u]:
			g[u][v] = w
			g[v][u] = w
		else:
			g[u][v] = min(g[u][v], w)
			g[v][u] = min(g[v][u], w)
	return g

def search(g, bv, ev):
	pq = []
	ps = {ev: ev}
	ws = {ev: 0}
	heappush(pq, (0, ev))
	while pq:
		(w, u) = heappop(pq)
		if u == bv:
			return ps
		if u not in g:
			continue
		for v in g[u]:
			cw = ws[u] + g[u][v]
			if v not in ws or cw < ws[v]:
				heappush(pq, (cw, v))
				ps[v] = u
				ws[v] = cw
	return {}

def path(bv, ev, ps):
	p = [bv]
	while bv != ev:
		bv = ps[bv]
		p.append(bv)
	return p

def test_case(nv, ne):
	bv = 1
	ev = nv
	g = graph(ne)
	ps = search(g, bv, ev)
	if not ps:
		print('-1 ')
		return
	print(bv, end=' ')
	while bv != ev:
		bv = ps[bv]
		print(bv, end=' ')
	print()

def main():
	for s in stdin:
		test_case(*(int(v) for v in s.split()))
main()


import heapq
inf = 10 ** 16
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 5)]
d = [0] * (n + 15)
vst = [False] * (n + 15)
trace = [-1] * (n + 15)

def dijsktra(s, t):
	for x in range(1, n + 1):
		d[x] = inf
		vst[x] = False
		trace[x] = -1
	d[s] = 0
	q = [(d[s], s)]
	while q:
		(C, u) = heapq.heappop(q)
		if C > d[u]:
			continue
		vst[u] = True
		for (v, c) in g[u]:
			if not vst[v] and C + c < d[v]:
				d[v] = C + c
				trace[v] = u
				heapq.heappush(q, (d[v], v))
for _ in range(m):
	(u, v, c) = map(int, input().split())
	g[u].append((v, c))
	g[v].append((u, c))
dijsktra(1, n)
if d[n] == inf:
	print(-1)
else:
	path = []
	path.append(n)
	while trace[n] != -1:
		path.append(trace[n])
		n = trace[n]
	path.reverse()
	for x in path:
		print(x, end=' ')


import heapq

def tezzzz():
	test = [(4, 2), (6, 0), (2, 8), (-9, 2), (8, 4), (1, 5), (6, 1), (10, -5)]
	heapq.heapify(test)
	while test:
		print(heapq.heappop(test))

def smaller(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	if a < b:
		return a
	return b

def find(adj_list, s):
	n = len(adj_list)
	d = []
	p = []
	for i in range(n):
		d.append(MAX)
		p.append(0)
	d[s] = 0
	vertex_queue = []
	heapq.heappush(vertex_queue, (d[s], s))
	while vertex_queue:
		tmp = heapq.heappop(vertex_queue)
		u = tmp[1]
		w = tmp[0]
		if w != d[u]:
			continue
		k = len(adj_list[u])
		for i in range(k):
			v = adj_list[u][i][0]
			if d[v] > d[u] + adj_list[u][i][1]:
				d[v] = d[u] + adj_list[u][i][1]
				p[v] = u
				heapq.heappush(vertex_queue, (d[v], v))
	return (d, p)

def main():
	tmp = input().split()
	n = int(tmp[0])
	m = int(tmp[1])
	adj_list = []
	for i in range(n):
		adj_list.append([])
	for i in range(m):
		tmp = input().split()
		u = int(tmp[0]) - 1
		v = int(tmp[1]) - 1
		w = int(tmp[2])
		adj_list[u].append((v, w))
		adj_list[v].append((u, w))
	s = 0
	(d, p) = find(adj_list, s)
	e = n - 1
	res = []
	if d[e] == MAX:
		print(-1)
	else:
		while e != 0:
			res.append(e)
			e = p[e]
		res.append(0)
		res.reverse()
		for i in range(len(res)):
			print(res[i] + 1, end=' ')
MAX = 9999999999999999
main()


from heapq import heappop, heappush
q = []
(n, m) = map(int, input().split())
el = [[] for i in range(n + 1)]
v = [False] * (n + 1)
bt = [-1] * (n + 1)
ml = [int(2e+20) for i in range(n + 1)]
d = None
for i in range(m):
	(a, b, w) = map(int, input().split())
	el[a].append((b, w))
	el[b].append((a, w))
heappush(q, (0, 1, -1))
while len(q):
	(z, x, r) = heappop(q)
	v[x] = True
	if z < ml[x]:
		(ml[x], bt[x]) = (z, r)
	if x == n:
		d = z
		break
	for (t, o) in el[x]:
		if not v[t]:
			heappush(q, (z + o, t, x))
p = []
a = n
if d is None:
	print(-1)
else:
	while a != -1:
		p.append(a)
		a = bt[a]
	p.reverse()
	print(' '.join(map(str, p)))


import heapq as hq
Inf = float('inf')

def dijkstra(n, adj, src):
	d = [Inf] * (n + 1)
	d[src] = 0
	q = []
	parent = [None] * (n + 1)
	hq.heappush(q, (d[src], src))
	while q:
		(_, u) = hq.heappop(q)
		for (v, w) in adj[u]:
			if d[v] > d[u] + w:
				d[v] = d[u] + w
				hq.heappush(q, (d[v], v))
				parent[v] = u
	return parent

def pathPrint(v, parent):
	path = []
	while v is not None:
		path.append(v)
		v = parent[v]
	l = len(path)
	for i in range(l):
		print(path[l - i - 1], end=' ')
(n, m) = map(int, input().split())
adj = {}
for i in range(1, n + 1):
	adj[i] = []
for _ in range(m):
	(u, v, w) = map(int, input().split())
	adj[u].append([v, w])
	adj[v].append([u, w])
parent = dijkstra(n, adj, 1)
if parent[n] == None:
	print('-1')
else:
	pathPrint(n, parent)


import heapq
import sys

def dijkstra(adj, source, target):
	INF = ((1 << 63) - 1) // 2
	n = len(adj)
	pred = [-1 for x in range(n)]
	dist = [INF for i in range(n)]
	dist[source] = 0
	Q = []
	heapq.heappush(Q, [dist[source], source])
	while Q:
		u = heapq.heappop(Q)
		u_dist = u[0]
		u_id = u[1]
		if u_id == target:
			break
		if u_dist > dist[u_id]:
			continue
		for v in adj[u_id]:
			v_id = v[0]
			w_uv = v[1]
			if dist[u_id] + w_uv < dist[v_id]:
				dist[v_id] = dist[u_id] + w_uv
				heapq.heappush(Q, [dist[v_id], v_id])
				pred[v_id] = u_id
	if dist[target] == INF:
		print(-1)
	else:
		st = []
		node = target
		while True:
			st.append(node)
			node = pred[node]
			if node == -1:
				break
		for num in reversed(st):
			print(num + 1, end=' ')
(n, m) = map(int, sys.stdin.readline().split())
adj = [[] for x in range(n)]
for i in range(m):
	(a, b, w) = map(int, input().split())
	adj[a - 1].append([b - 1, w])
	adj[b - 1].append([a - 1, w])
source = 0
target = n - 1
dijkstra(adj, 0, n - 1)


import os
import sys
from io import BytesIO, IOBase
from heapq import *

def main():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		graph[a].append((c, b))
		graph[b].append((c, a))
	parent = [-1] * (n + 1)
	dist = [10 ** 20] * (n + 1)
	start = 1
	end = n
	dist[start] = 0
	visited = [0] * (n + 1)
	heap = [(0, 1)]
	heapify(heap)
	while heap:
		z = heappop(heap)[1]
		if visited[z]:
			continue
		visited[z] = 1
		if z == end:
			break
		for item in graph[z]:
			(x, y) = item
			if not visited[y] and dist[y] > x + dist[z]:
				dist[y] = dist[z] + x
				heappush(heap, (dist[y], y))
				parent[y] = z
	ans = []
	while end != -1:
		ans.append(end)
		end = parent[end]
	if ans[-1] == start:
		ans.reverse()
		print(*ans)
	else:
		print(-1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin
from heapq import heappop, heappush
INF = float('inf')

def dijkstra(G, s):
	ans = [INF for j in G]
	ans[s] = 0
	prev = [None for _ in G]
	visited = [False for _ in G]
	heap = [(0, s)]
	while len(heap) != 0:
		(d, u) = heappop(heap)
		if visited[u] == False:
			for (v, dv) in G[u]:
				if d + dv < ans[v]:
					ans[v] = d + dv
					heappush(heap, (ans[v], v))
					prev[v] = u
			visited[u] = True
	return prev

def solve(l):
	ans = list()
	i = len(l) - 1
	ans.append(i)
	while l[i] != None:
		ans.append(l[i])
		i = l[i]
	return ans

def main():
	(lenv, lene) = map(int, stdin.readline().split())
	G = [list() for _ in range(lenv)]
	for _ in range(lene):
		(u, v, d) = map(int, stdin.readline().split())
		G[u - 1].append((v - 1, d))
		G[v - 1].append((u - 1, d))
	temp = dijkstra(G, 0)
	if temp[lenv - 1] != None:
		ppr = solve(temp)
		i = len(ppr) - 1
		while i >= 0:
			if i == 0:
				print(ppr[i] + 1, end='')
			else:
				print(ppr[i] + 1, end=' ')
			i -= 1
	else:
		print('-1')
main()


from heapq import *
graph = {}
cost = []
pp = []

def readline_int():
	data = str(input()).split(' ')
	for i in range(len(data)):
		data[i] = int(data[i])
	return data

def add_edge(u, v, w):
	if u not in graph:
		graph[u] = []
	graph[u].append([w, v])
	if v not in graph:
		graph[v] = []
	graph[v].append([w, u])

def dijkstra(st, ed):
	q = [(0, st)]
	cost[st] = 0
	while len(q) > 0:
		(w, u) = heappop(q)
		if cost[u] < w:
			continue
		if ed == u:
			return w
		if u not in graph:
			continue
		for e in graph[u]:
			if cost[e[1]] <= w + e[0]:
				continue
			cost[e[1]] = w + e[0]
			pp[e[1]] = u
			heappush(q, (w + e[0], e[1]))
	return -1
(n, m) = readline_int()
for i in range(m):
	(u, v, w) = readline_int()
	add_edge(u, v, w)
for u in range(n + 1):
	cost.append(1e+18)
	pp.append(-1)
ans = dijkstra(1, n)
if ans != -1:
	path = []
	v = n
	while v != -1:
		path.append(str(v))
		v = pp[v]
	print(' '.join(reversed(path)))
else:
	print(ans)


from collections import defaultdict
from heapq import *

def dijakstra(n, edges, s):
	distance = [-1] * (n + 1)
	distance[s] = 0
	q = [(distance[s], s)]
	parent = {i: -1 for i in range(1, n + 1)}
	visited = [False] * (n + 1)
	while q:
		(now_dis, now_node) = heappop(q)
		for neighbour in edges[now_node]:
			(curr_weight, curr_node) = (neighbour[1], neighbour[0])
			if distance[curr_node] == -1:
				parent[curr_node] = now_node
				distance[curr_node] = distance[now_node] + curr_weight
				heappush(q, (distance[curr_node], curr_node))
			elif distance[now_node] + curr_weight < distance[curr_node]:
				parent[curr_node] = now_node
				distance[curr_node] = distance[now_node] + curr_weight
				heappush(q, (distance[curr_node], curr_node))
	return parent

def backtrace(parent, start, end):
	path = [end]
	while path[-1] != start and path[-1] > 0:
		path.append(parent[path[-1]])
	path.reverse()
	return path
(n, m) = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
	(u, v, w) = map(int, input().split())
	graph[u].append([v, w])
	graph[v].append([u, w])
parent = dijakstra(n, graph, 1)
if parent[n] == -1:
	print(-1)
else:
	print(*backtrace(parent, 1, n))


import os
import sys
import copy
import heapq
from collections import defaultdict

def solve():
	(n, m) = map(lambda x: int(x), input().split())
	G = {}
	for i in range(m):
		(a, b, c) = map(lambda x: int(x), input().split())
		if a > b:
			(a, b) = (b, a)
		if (a, b) in G:
			G[a, b] = min([G[a, b], c])
		else:
			G[a, b] = c
	Glist = defaultdict(list)
	for (k, v) in G.items():
		Glist[k[0]].append((k[1], v))
		Glist[k[1]].append((k[0], v))
	pre = [-1 for i in range(n + 1)]

	def dijkstra(s, e):
		(q, seen) = ([(0, -1, s)], set())
		while q:
			(cost, pe, v) = heapq.heappop(q)
			if v not in seen:
				seen.add(v)
				pre[v] = pe
				if v == e:
					return cost
				for (v2, c) in Glist[v]:
					if v2 not in seen:
						heapq.heappush(q, (cost + c, v, v2))
		return -1
	re = dijkstra(1, n)
	if re == -1:
		print(-1)
	else:
		ans = []
		k = n
		while pre[k] != -1:
			ans.append(k)
			k = pre[k]
		ans.append(1)
		ans.reverse()
		for vertex in ans:
			print(vertex, end=' ')
solve()


from math import inf
from heapq import heappop, heappush

def calc_path(parents):
	output = ['-1']
	if parents[-1] != -1:
		i = len(parents) - 1
		output = []
		while i != -1:
			output.append(str(i + 1))
			i = int(parents[i])
	output.reverse()
	return ' '.join(output)
(n, m) = [int(x) for x in input().split()]
dist = []
vis = []
pars = []
graph = {}
for i in range(n):
	dist.append(inf)
	vis.append(False)
	pars.append(-1)
	graph[i] = {}
for i in range(m):
	(n1, n2, v) = [int(x) for x in input().split()]
	graph[n1 - 1][n2 - 1] = v
	graph[n2 - 1][n1 - 1] = v
	dist[0] = 0
heap = [(0, 0)]
while len(heap) > 0:
	no = heappop(heap)[1]
	if not vis[no]:
		vis[no] = True
		for j in graph[no]:
			if not vis[j] and dist[j] > dist[no] + graph[no][j]:
				dist[j] = dist[no] + graph[no][j]
				pars[j] = no
				heappush(heap, (dist[j], j))
print(calc_path(pars))


import heapq

def dijkstra(graph, source):
	distances = [(float('inf'), None) for i in range(len(graph))]
	distances[0] = (0, None)
	h = []
	heapq.heappush(h, (0, source))
	while len(h) > 0:
		(w, node) = heapq.heappop(h)
		for (i, edge) in graph[node]:
			if edge == -1:
				continue
			tmp = w + edge
			if distances[i][0] > tmp:
				distances[i] = (tmp, node)
				heapq.heappush(h, (tmp, i))
	return distances

def reconstruct(distances):
	path = []
	nxt = (distances[-1], len(distances) - 1)
	while True:
		path.append(str(nxt[1] + 1))
		if nxt[0][1] is None:
			break
		nxt = (distances[nxt[0][1]], nxt[0][1])
	return path
(v, e) = map(int, input().split())
graph = [[] for i in range(v)]
for i in range(e):
	(o, d, w) = map(int, input().split())
	o -= 1
	d -= 1
	graph[o].append((d, w))
	graph[d].append((o, w))
path = reconstruct(dijkstra(graph, 0))
if path[-1] != '1':
	print('-1')
else:
	path.reverse()
	print(' '.join(path))


from heapq import *
inf = 1 << 40
(n, m) = map(int, input().split())
k = n + 1
g = [[] for i in range(k)]
for j in range(m):
	(u, v, l) = map(int, input().split())
	g[u].append((v, l))
	g[v].append((u, l))
d = [inf] * k
d[1] = 0
p = [0] * k
q = [1]
while q:
	h = heappop(q)
	(v, l) = (h % k, h // k)
	if d[v] != l:
		continue
	for (u, l) in g[v]:
		s = d[v] + l
		if s < d[u]:
			(d[u], p[u]) = (s, v)
			heappush(q, k * s + u)
if d[n] == inf:
	print(-1)
else:
	(u, t) = (n, [])
	while u:
		t.append(u)
		u = p[u]
	t.reverse()
	print(' '.join(map(str, t)))


import heapq

def path(source, destination):
	path = []
	par = []
	dis = []
	vis = []
	for i in range(n + 1):
		dis.append(1000000000000)
		vis.append(False)
		par.append(-1)
	dis[source] = 0
	q = []
	heapq.heappush(q, (0, source))
	while q:
		next_item = heapq.heappop(q)
		node = next_item[1]
		if vis[node]:
			continue
		vis[node] = True
		i = 1
		flag = False
		for item in cell_adj[node]:
			if item != 0:
				if dis[item] > dis[node] + cell_wei[node][i]:
					dis[item] = min(dis[item], dis[node] + cell_wei[node][i])
					par[item] = node
					heapq.heappush(q, (dis[item], item))
				i = i + 1
	path.append(destination)
	while par[destination] != -1:
		path.append(par[destination])
		destination = par[destination]
	path.reverse()
	if path[0] != 1:
		print(-1)
		return
	for len in path:
		print(len)
	return path
(n, m) = input().split()
n = int(n)
m = int(m)
cols = 1
cell_adj = [[0 for i in range(1)] for j in range(n + 1)]
cell_wei = [[0 for k in range(1)] for l in range(n + 1)]
for i in range(m):
	(a, b, w) = input().split()
	a = int(a)
	b = int(b)
	w = int(w)
	cell_adj[a].append(b)
	cell_adj[b].append(a)
	cell_wei[a].append(w)
	cell_wei[b].append(w)
ans = path(1, n)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [tuple(map(int, l.split())) for l in sys.stdin]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, m) = LI()
	e = collections.defaultdict(list)
	for _ in range(m):
		(a, b, c) = LI()
		e[a].append((b, c))
		e[b].append((a, c))

	def search(s):
		d = collections.defaultdict(lambda : inf)
		d[s] = 0
		q = []
		heapq.heappush(q, (0, s))
		v = collections.defaultdict(bool)
		while len(q):
			(k, u) = heapq.heappop(q)
			if v[u]:
				continue
			v[u] = True
			for (uv, ud) in e[u]:
				if v[uv]:
					continue
				vd = k + ud
				if d[uv] > vd:
					d[uv] = vd
					heapq.heappush(q, (vd, uv))
		return d
	d = search(1)
	if d[n] == inf:
		return -1
	r = [n]
	t = n
	while t != 1:
		for (k, v) in e[t]:
			if d[k] == d[t] - v:
				r.append(k)
				t = k
				break
	return ' '.join(map(str, r[::-1]))
print(main())


from heapq import *
inputs = [int(x) for x in input().split()]
vertice = inputs[0]
edges = inputs[1]
adjacency_list = {}
for x in range(edges):
	edge = [int(x) for x in input().split()]
	start = edge[0]
	end = edge[1]
	weight = edge[2]
	if start in adjacency_list:
		adjacency_list[start].append((end, weight))
	else:
		adjacency_list[start] = []
		adjacency_list[start].append((end, weight))
	if end in adjacency_list:
		adjacency_list[end].append((start, weight))
	else:
		adjacency_list[end] = []
		adjacency_list[end].append((start, weight))

def dijkstra(start, end):
	q = [(0, start)]
	visited = {}
	visited[start] = (0, start)
	if not end in adjacency_list:
		print('-1')
		return {}
	if start == end:
		print(start)
		return {start: (0, start)}
	while len(q) != 0:
		current = heappop(q)[1]
		for (to, weight) in adjacency_list[current]:
			new_dist = visited[current][0] + weight
			if not to in visited or visited[to][0] > new_dist:
				visited[to] = (new_dist, current)
				heappush(q, (new_dist, to))
	path = []
	if end in visited:
		current = end
		while current != 1:
			path.append(str(current))
			current = visited[current][1]
		path.append('1')
	else:
		print('-1')
	print(' '.join(path[::-1]))

def backtrack(visited, end):
	if end in visited:
		current = end
		while current != 1:
			path.append(str(current))
			current = visited[current][1]
		path.append('1')
	else:
		print('-1')
visited = dijkstra(1, vertice)


from heapq import heappop, heappush

def int_line():
	return map(int, input().split())
(nodes, edges) = int_line()
graph = [[] for x in range(nodes)]
for x in range(edges):
	(left, right, cost) = int_line()
	left -= 1
	right -= 1
	graph[left].append((right, cost))
	graph[right].append((left, cost))
visited = [False for x in range(nodes)]
previous = [-1 for x in range(nodes)]
pq = list()
heappush(pq, (0, 0, -1))
path_found = False
while pq:
	(path_cost, node, prev) = heappop(pq)
	if visited[node]:
		continue
	visited[node] = True
	previous[node] = prev
	if node == nodes - 1:
		path_found = True
		break
	for (nxt, cost) in graph[node]:
		if not visited[nxt]:
			heappush(pq, (path_cost + cost, nxt, node))
if not path_found:
	print(-1)
	exit(0)
	quit()
path = []
current = nodes - 1
while current != -1:
	path.append(str(current + 1))
	current = previous[current]
path.reverse()
print(' '.join(path))


import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def dijkstra(graph, start=0):
	n = len(graph)
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0.0
	queue = [(0.0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
	(a, b, w) = map(int, input().split())
	graph[a - 1].append((b - 1, w))
	graph[b - 1].append((a - 1, w))
(_, parents) = dijkstra(graph)
if parents[n - 1] == -1:
	print(-1)
else:
	(res, parent) = ([], n - 1)
	while parent != parents[0]:
		res.append(parent + 1)
		parent = parents[parent]
	res.reverse()
	print(*res)


from heapq import *
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(m):
	(x, y, w) = map(int, input().split())
	if x != y:
		g[x].append((y, w))
		g[y].append((x, w))
path = [0] * (n + 1)
dis = [float('inf')] * (n + 1)
hp = [(0, 1)]
while hp:
	(dcur, cur) = heappop(hp)
	for (v, w) in g[cur]:
		if dcur + w < dis[v]:
			dis[v] = dcur + w
			path[v] = cur
			heappush(hp, (dis[v], v))
l = [n]
x = n
if path[n] > 0:
	while x != 1:
		x = path[x]
		l.append(x)
	print(*l[::-1])
else:
	print(-1)


import sys
from collections import deque
input = sys.stdin.readline
INF = 10 ** 9
from heapq import heappop, heappush

def dijkstra(n, graph, start):
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)

def desopo_pape(graph):
	n = len(graph)
	par = [-1] * n
	dist = [INF] * n
	dist[1] = 0
	processed = set()
	processing = deque()
	to_process = set()
	m = [2] * n
	processing.append(1)
	m[1] = 1
	for i in range(2, n):
		to_process.add(i)
	while processing:
		u = processing.popleft()
		for (v, w) in graph[u]:
			if dist[u] + w >= dist[v]:
				continue
			par[v] = u
			dist[v] = dist[u] + w
			if m[v] == 0:
				processed.discard(v)
				processing.appendleft(v)
				m[v] = 1
			elif m[v] == 2:
				to_process.discard(v)
				processing.append(v)
				m[v] = 1
		processed.add(u)
		m[u] = 0
	return par

def main():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	for i in range(m):
		(u, v, w) = map(int, input().split())
		graph[u].append((v, w))
		graph[v].append((u, w))
	(_, par) = dijkstra(n + 1, graph, 1)
	if par[n] == -1:
		print(-1)
	else:
		path = deque()
		path.append(n)
		while n != 1:
			n = par[n]
			path.appendleft(n)
		print(*path)
	return 0
main()


from heapq import *
INF = 1 << 60
(n, m) = map(int, input().split())
(g, d, p, q) = ([[] for _ in range(n)], [0] + [INF] * n, [-1] * n, [(0, 0)])
for _ in range(m):
	(u, v, t) = map(int, input().split())
	g[u - 1] += [(t, v - 1)]
	g[v - 1] += [(t, u - 1)]
while q:
	(di, u) = heappop(q)
	if di < d[u]:
		continue
	for e in g[u]:
		(t, v) = (d[u] + e[0], e[1])
		if t < d[v]:
			(d[v], p[v]) = (t, u)
			heappush(q, (d[v], v))
if d[n - 1] == INF:
	print(-1)
else:
	(x, a) = (n - 1, [])
	while x != -1:
		a += [x + 1]
		x = p[x]
	a.reverse()
	print(' '.join(map(str, a)))


import heapq

def dij():
	min_q = []
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	adj = [list() for _ in range(n)]
	dist = [None] * n
	pred = [None] * n
	for i in range(m):
		(a, b, w) = input().split(' ')
		a = int(a) - 1
		b = int(b) - 1
		w = int(w)
		adj[a].append((b, w))
		adj[b].append((a, w))
		if i == 0:
			heapq.heappush(min_q, (0, 0))
	seen = [False] * n
	start = 0
	end = n - 1
	dist[start] = 0
	pred[start] = -1
	while seen[end] is False:
		try:
			(cur_dist, cur) = heapq.heappop(min_q)
			seen[cur] = True
		except IndexError:
			return -1
		for (node, weight) in adj[cur]:
			if dist[node] is None:
				dist[node] = weight + dist[cur]
				heapq.heappush(min_q, (dist[node], node))
				pred[node] = cur
			elif dist[node] > dist[cur] + weight:
				dist[node] = weight + dist[cur]
				heapq.heappush(min_q, (dist[node], node))
				pred[node] = cur
	path = []
	cur = end
	while cur != -1:
		path.append(str(cur + 1))
		cur = pred[cur]
	path = path[::-1]
	return ' '.join(path)
print(dij())


from sys import stdin
import heapq

def main():
	(n, m) = map(int, stdin.readline().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(m):
		(x, y, w) = map(int, stdin.readline().split())
		if x == y:
			continue
		adj[x].append((y, w))
		adj[y].append((x, w))
	max_val = 10 ** 18
	dist = [max_val] * (n + 1)
	dist[1] = 0
	q = []
	heapq.heappush(q, (0, 1))
	process = [False] * (n + 1)
	prev = [i for i in range(n + 1)]
	while q:
		(cd, cv) = heapq.heappop(q)
		if cd != dist[cv]:
			continue
		for p in adj[cv]:
			nb = p[0]
			w = p[1]
			if dist[cv] + w < dist[nb]:
				dist[nb] = dist[cv] + w
				prev[nb] = cv
				heapq.heappush(q, (dist[nb], nb))
	if dist[n] == max_val:
		print(-1)
	else:
		ans = []
		cv = n
		while prev[cv] != cv:
			ans.append(cv)
			cv = prev[cv]
		ans.append(1)
		ans.reverse()
		print(*ans)
main()


import heapq
from sys import stdin, stdout

def dijkstra(adj, source, target):
	INF = ((1 << 63) - 1) // 2
	n = len(adj)
	pred = [-1 for x in range(n)]
	dist = [INF for i in range(n)]
	dist[source] = 0
	Q = []
	heapq.heappush(Q, [dist[source], source])
	while Q:
		u = heapq.heappop(Q)
		u_dist = u[0]
		u_id = u[1]
		if u_id == target:
			break
		if u_dist > dist[u_id]:
			continue
		for v in adj[u_id]:
			v_id = v[0]
			w_uv = v[1]
			if dist[u_id] + w_uv < dist[v_id]:
				dist[v_id] = dist[u_id] + w_uv
				heapq.heappush(Q, [dist[v_id], v_id])
				pred[v_id] = u_id
	if dist[target] == INF:
		stdout.write('-1\n')
	else:
		st = []
		node = target
		while True:
			st.append(str(node + 1))
			node = pred[node]
			if node == -1:
				break
		path = st[::-1]
		stdout.write(' '.join(path) + '\n')

def main():
	(n, m) = [int(x) for x in stdin.readline().split()]
	adj = [[] for x in range(n)]
	for i in range(m):
		(a, b, w) = [int(x) for x in stdin.readline().split()]
		adj[a - 1].append([b - 1, w])
		adj[b - 1].append([a - 1, w])
	source = 0
	target = n - 1
	dijkstra(adj, 0, n - 1)
main()


import sys
import heapq

def djikstra():
	data = [line.rstrip().split() for line in sys.stdin.readlines()]
	data = [[int(x) for x in row] for row in data]
	input_1 = data[0]
	num_vertices = input_1[0]
	num_edges = input_1[1]
	adj = [[] for i in range(num_vertices)]
	for i in range(1, len(data)):
		v1 = data[i][0] - 1
		v2 = data[i][1] - 1
		cost = data[i][2]
		adj[v1].append((v2, cost))
		adj[v2].append((v1, cost))
	n = len(adj)
	d = [100000000000 for i in range(num_vertices)]
	p = [-1 for i in range(num_vertices)]
	d[0] = 0
	q = []
	heapq.heappush(q, (0, 0))
	while len(q) > 0:
		val = heapq.heappop(q)
		cost = val[0]
		v = val[1]
		if cost != d[v]:
			continue
		for edge in adj[v]:
			to = edge[0]
			edge_len = edge[1]
			if d[v] + edge_len < d[to]:
				d[to] = d[v] + edge_len
				p[to] = v
				heapq.heappush(q, (d[to], to))
	v = num_vertices - 1
	path = []
	while v != 0:
		path.append(str(v + 1))
		v = p[v]
		if v == -1:
			print('-1')
			return
	path.append('1')
	print(' '.join(reversed(path)))
djikstra()


from heapq import heappop, heappush
(n, m) = map(int, input().split())
mat = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	mat[a].append((b, c))
	mat[b].append((a, c))
visi = [False] * n
desc = [-1] * n
que = []
heappush(que, (0, 0, -1))
while que:
	(cost, nodo, de) = heappop(que)
	if visi[nodo]:
		continue
	visi[nodo] = True
	desc[nodo] = de
	for (b, c) in mat[nodo]:
		heappush(que, (cost + c, b, nodo))
x = n - 1
resp = [n]
while x > 0:
	resp.append(desc[x] + 1)
	x = desc[x]
if resp[-1] == 0:
	print(-1)
else:
	print(*reversed(resp))


from heapq import heappush, heappop
from sys import stdin, exit
(n, m) = map(int, stdin.readline().rstrip().split())
graph = {}
visited = set()
path_exists = False
for line in range(0, m):
	(a, b, w) = map(int, stdin.readline().rstrip().split())
	if a not in graph:
		graph[a] = [(b, w)]
	else:
		graph[a].append((b, w))
	if b not in graph:
		graph[b] = [(a, w)]
	else:
		graph[b].append((a, w))
if 1 not in graph:
	print(str(-1))
	exit()
priority_q = []
heappush(priority_q, (0, 1, -1))
path = ''
path_so_far = {}
while priority_q:
	current = heappop(priority_q)
	if current[1] not in visited:
		path_so_far[current[1]] = (current[0], current[2])
		if current[1] == n:
			path_exists = True
			break
		else:
			visited.add(current[1])
			for (neighbor, priority) in graph[current[1]]:
				heappush(priority_q, (priority + current[0], neighbor, current[1]))
path_stack = []
path_stack.append(n)
one_not_in = False
if path_exists:
	while not one_not_in:
		prev_node = path_so_far[path_stack[len(path_stack) - 1]]
		if prev_node[1] == 1:
			one_not_in = True
		path_stack.append(prev_node[1])
	while path_stack:
		print(path_stack.pop(), end=' ')
else:
	print(str(-1))


import heapq as h

def Dijkstra(n, m, graph):
	to_check = []
	parents = [0] * (n + 1)
	paths = [float('inf')] * (n + 1)
	visited = [False] * (n + 1)
	paths[1] = 0
	parents[1] = 1
	h.heappush(to_check, (0, 1))
	while len(to_check) != 0:
		actual = h.heappop(to_check)[1]
		if visited[actual] == True:
			continue
		visited[actual] = True
		for verticle in graph[actual]:
			neighbour = verticle[1]
			cost = verticle[0]
			if paths[actual] + cost < paths[neighbour]:
				paths[neighbour] = paths[actual] + cost
				parents[neighbour] = actual
				h.heappush(to_check, (paths[neighbour], neighbour))
	return parents

def main():
	(n, m) = list(map(int, input().split()))
	graf = []
	for x in range(n + 1):
		graf.append([])
	for line in range(m):
		data = list(map(int, input().split()))
		graf[data[0]].append((data[2], data[1]))
		graf[data[1]].append((data[2], data[0]))
	parents = Dijkstra(n, m, graf)
	v = n
	anserw = [str(v)]
	fail = False
	while v != 1:
		if parents[v] == 0:
			fail = True
			break
		anserw.append(str(parents[v]))
		v = parents[v]
	if not fail:
		to_print = reversed(anserw)
		print(' '.join(to_print))
	else:
		print('-1')
main()


from heapq import heappush, heappop
import sys
(n, m) = map(int, input().split())
parent = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]
dist = [2 ** 40] * (n + 1)
dist[1] = 0
H = [(0, 1)]
for _ in range(m):
	(a, b, w) = map(int, input().split())
	graph[a].append((b, w))
	graph[b].append((a, w))
while H:
	(weight, node) = heappop(H)
	for (nn, ww) in graph[node]:
		ww += weight
		if ww < dist[nn]:
			dist[nn] = ww
			parent[nn] = node
			heappush(H, (ww, nn))
if parent[n] == 0:
	print(-1)
else:
	ans = [n]
	p = n
	while p != 1:
		p = parent[p]
		ans.append(p)
	print(*ans[::-1])


import sys
from collections import defaultdict
from heapq import *
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
d = defaultdict(list)
for _ in range(m):
	(u, v, w) = map(int, input().split())
	d[u].append((v, w))
	d[v].append((u, w))
dis = [10 ** 18 for i in range(n + 1)]
dis[1] = 0
vis = [False for i in range(n + 1)]
par = [-1 for i in range(n + 1)]
h = []
heappush(h, (0, 1))
while h:
	(currDis, v) = heappop(h)
	if vis[v]:
		continue
	vis[v] = True
	for (u, w) in d[v]:
		if w + currDis < dis[u]:
			dis[u] = w + currDis
			heappush(h, (dis[u], u))
			par[u] = v
if dis[n] == 10 ** 18:
	print(-1)
else:
	l = []
	while n > 0:
		l.append(n)
		n = par[n]
	l.reverse()
	print(*l)


import heapq
from sys import stdin, stdout

def dfs_iterative(adjLists, s, target, marked):
	stack = [s]
	while stack:
		u = stack.pop()
		if not marked[u]:
			marked[u] = True
			if u == target:
				break
			for w in adjLists[u]:
				if not marked[w[0]]:
					stack.append(w[0])

def exists_path(adj, source, target):
	n = len(adj)
	marked = [False for _ in range(n)]
	dfs_iterative(adj, source, target, marked)
	return marked[target]

def dijkstra(adj, source, target):
	if not exists_path(adj, source, target):
		stdout.write('-1\n')
		return
	n = len(adj)
	INF = ((1 << 63) - 1) // 2
	pred = [x for x in range(n)]
	dist = [INF for x in range(n)]
	pred_b = [x for x in range(n)]
	dist_b = [INF for x in range(n)]
	dist[source] = 0
	dist_b[target] = 0
	Q = []
	Q_b = []
	S = set()
	S_b = set()
	heapq.heappush(Q, [dist[source], source])
	heapq.heappush(Q_b, [dist_b[target], target])
	while True:
		u = heapq.heappop(Q_b)
		u_dist = u[0]
		u_id = u[1]
		S_b.add(u_id)
		if u_dist == dist_b[u_id]:
			if u_id in S:
				break
			for v in adj[u_id]:
				v_id = v[0]
				w_uv = v[1]
				if dist_b[u_id] + w_uv < dist_b[v_id]:
					dist_b[v_id] = dist_b[u_id] + w_uv
					heapq.heappush(Q_b, [dist_b[v_id], v_id])
					pred_b[v_id] = u_id
		u = heapq.heappop(Q)
		u_dist = u[0]
		u_id = u[1]
		S.add(u_id)
		if u_dist == dist[u_id]:
			if u_id in S_b:
				break
			for v in adj[u_id]:
				v_id = v[0]
				w_uv = v[1]
				if dist[u_id] + w_uv < dist[v_id]:
					dist[v_id] = dist[u_id] + w_uv
					heapq.heappush(Q, [dist[v_id], v_id])
					pred[v_id] = u_id
	nodes_in_Q = set()
	while Q:
		u = heapq.heappop(Q)
		u_id = u[1]
		nodes_in_Q.add(u_id)
	nodes_in_Q_b = set()
	while Q_b:
		u = heapq.heappop(Q_b)
		u_id = u[1]
		nodes_in_Q_b.add(u_id)
	candidates = (S | nodes_in_Q) & (S_b | nodes_in_Q_b)
	min_dist = INF
	min_node = 'none'
	for node in candidates:
		middle_dist = dist[node] + dist_b[node]
		if middle_dist < min_dist:
			min_dist = middle_dist
			min_node = node
	st = []
	node = min_node
	while True:
		st.append(str(node + 1))
		if node == pred[node]:
			break
		node = pred[node]
	path_forward = st[::-1]
	st = []
	node = min_node
	while True:
		st.append(str(node + 1))
		if node == pred_b[node]:
			break
		node = pred_b[node]
	path = ' '.join(path_forward) + ' ' + ' '.join(st[1:])
	stdout.write(path + '\n')

def main():
	(n, m) = [int(c) for c in input().split()]
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(a, b, w) = [int(c) for c in stdin.readline().split()]
		adj[a - 1].append((b - 1, w))
		adj[b - 1].append((a - 1, w))
	source = 0
	target = n - 1
	dijkstra(adj, source, target)
main()


import heapq
from sys import stdin, stdout
from operator import itemgetter

def dijkstra(adj, source, target):
	n = len(adj)
	INF = ((1 << 63) - 1) // 2
	pred = [x for x in range(n)]
	dist = [INF for x in range(n)]
	visited = set()
	dist[source] = 0
	Q = []
	heapq.heappush(Q, [dist[source], source])
	while Q:
		u = heapq.heappop(Q)
		u_dist = u[0]
		u_id = u[1]
		visited.add(u_id)
		if u_dist > dist[u_id]:
			continue
		if u_id == target:
			break
		for v in adj[u_id]:
			v_id = v[0]
			w_uv = v[1]
			if dist[u_id] + w_uv < dist[v_id]:
				dist[v_id] = dist[u_id] + w_uv
				heapq.heappush(Q, [dist[v_id], v_id])
				pred[v_id] = u_id
	if dist[target] == INF:
		stdout.write('-1\n')
	else:
		st = []
		node = target
		while True:
			st.append(str(node + 1))
			if node == pred[node]:
				break
			node = pred[node]
		path = st[::-1]
		stdout.write(' '.join(path) + '\n')

def main():
	(n, m) = [int(x) for x in stdin.readline().split()]
	graph_dicts_of_dicts = {u: {} for u in range(n)}
	for i in range(m):
		(a, b, w) = [int(c) for c in stdin.readline().split()]
		w = int(w)
		a -= 1
		b -= 1
		if not b in graph_dicts_of_dicts[a]:
			graph_dicts_of_dicts[a][b] = w
		else:
			graph_dicts_of_dicts[a][b] = min(graph_dicts_of_dicts[a][b], w)
		if not a in graph_dicts_of_dicts[b]:
			graph_dicts_of_dicts[b][a] = w
		else:
			graph_dicts_of_dicts[b][a] = min(graph_dicts_of_dicts[b][a], w)
	graph = [[] for u in range(n)]
	for u in range(n):
		for (v, w) in graph_dicts_of_dicts[u].items():
			graph[u].append((v, w))
	for u in range(n):
		graph[u].sort(key=itemgetter(1))
	source = 0
	target = n - 1
	dijkstra(graph, source, target)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from heapq import heapify, heappush as hp, heappop as pop

def dijsktra(x):
	q = []
	heapify([])
	hp(q, x)
	d[x[1]] = x[0]
	while len(q):
		(curd, cur) = pop(q)
		if curd > d[cur]:
			continue
		for i in adj[cur]:
			if curd + i[0] < d[i[1]]:
				d[i[1]] = curd + i[0]
				l[i[1]] = cur
				hp(q, [d[i[1]], i[1]])
(n, m) = map(int, input().split())
inf = 10 ** 11
d = [inf] * (n + 1)
adj = []
for i in range(n + 1):
	adj.append([])
for i in range(m):
	(x, y, w) = map(int, input().split())
	adj[x].append([w, y])
	adj[y].append([w, x])
l = [-1] * (n + 1)
dijsktra([0, 1])
if d[n] != inf:
	l1 = []
	i = n
	while i != -1:
		l1.append(i)
		i = l[i]
	print(*l1[::-1])
else:
	print(-1)


from sys import stdin
import heapq
(n, m) = [int(x) for x in stdin.readline().split()]
graph = [{} for x in range(n)]
for edge in range(m):
	(a, b, w) = [int(x) for x in stdin.readline().split()]
	a -= 1
	b -= 1
	graph[a][b] = w
	graph[b][a] = w

def dij(n, tu, graph):
	visited = [False for x in graph]
	weight = [float('inf') for x in graph]
	path = {}
	weight[n] = 0
	q = [(0, n)]
	while q:
		(w, node) = heapq.heappop(q)
		if not visited[node]:
			visited[node] = True
			for x in graph[node]:
				if w + graph[node][x] < weight[x]:
					heapq.heappush(q, (w + graph[node][x], x))
					weight[x] = w + graph[node][x]
					path[x] = node
	out = []
	cur = tu
	while cur in path:
		out.append(cur)
		cur = path[cur]
	return out[::-1]
result = dij(0, n - 1, graph)
if n == 1:
	print(1)
elif not result:
	print(-1)
else:
	print(' '.join([str(x + 1) for x in [0] + result]))


from heapq import heappop, heappush
q = []
(n, m) = map(int, input().split())
el = [[] for i in range(n + 1)]
v = [False] * (n + 1)
bt = [-1] * (n + 1)
ml = [int(2e+20) for i in range(n + 1)]
d = None
for i in range(m):
	(a, b, w) = map(int, input().split())
	el[a].append((b, w))
	el[b].append((a, w))
heappush(q, (0, 1, -1))
while len(q):
	c = heappop(q)
	v[c[1]] = True
	if c[0] < ml[c[1]]:
		ml[c[1]] = c[0]
		bt[c[1]] = c[2]
	if c[1] == n:
		d = c[0]
		break
	for e in el[c[1]]:
		if not v[e[0]]:
			heappush(q, (c[0] + e[1], e[0], c[1]))
p = []
a = n
if d is None:
	print(-1)
else:
	while a != -1:
		p.append(a)
		a = bt[a]
p.reverse()
print(' '.join(map(str, p)))


import heapq
h = []
params = [int(i) for i in input().split()]
edges = {i + 1: [10000000000000000, {}, False, i + 1, -1] for i in range(params[0])}
for i in range(params[1]):
	val = [int(j) for j in input().split()]
	amt = val[2]
	if val[1] in edges[val[0]][1]:
		amt = min(amt, edges[val[0]][1][val[1]])
		edges[val[0]][1][val[1]] = amt
	else:
		edges[val[0]][1].update({val[1]: amt})
	if val[0] in edges[val[1]][1]:
		amt = min(amt, edges[val[1]][1][val[0]])
		edges[val[1]][1][val[0]] = amt
	else:
		edges[val[1]][1].update({val[0]: amt})

def dijkstra():
	edges[1][0] = 0
	heapq.heappush(h, (edges[1][0], edges[1][3], edges[1][4]))
	while h:
		val = heapq.heappop(h)
		val = edges[val[1]]
		if val[3] == params[0]:
			return 0
		if val[2]:
			continue
		edges[val[3]][2] = True
		for key in edges[val[3]][1]:
			if not edges[key][2]:
				num = edges[val[3]][1][key] + edges[val[3]][0]
				if num < edges[key][0]:
					edges[key][0] = num
					edges[key][4] = val[3]
					heapq.heappush(h, (edges[key][0], edges[key][3]))
	return -1
if dijkstra() == -1:
	print(-1)
else:
	arr = [params[0]]
	val = edges[params[0]][4]
	while not val == -1:
		arr.append(str(val))
		val = edges[val][4]
	arr = reversed(arr)
	print(*arr, sep=' ')


from __future__ import division, print_function
import os
import sys
from heapq import heappop, heappush
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def dijkstra(graph, start=0):
	n = len(graph)
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)

def main():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n)]
	for i in range(m):
		(_a, _b, _w) = input().split()
		(a, b, w) = (int(_a) - 1, int(_b) - 1, float(_w))
		graph[a].append((b, w))
		graph[b].append((a, w))
	(_, parents) = dijkstra(graph)
	if parents[n - 1] == -1:
		print(-1)
	else:
		(res, parent) = ([], n - 1)
		while parent != parents[0]:
			res.append(parent + 1)
			parent = parents[parent]
		res.reverse()
		print(*res)
main()


from heapq import heappush, heappop
oo = 18 ** 12
(n, m) = [int(x) for x in input().split()]
adj = [[] for _ in range(n)]
p = [-1] * n
d = [0] + [oo] * (n - 1)
for _ in range(m):
	(u, v, w) = map(int, input().split())
	adj[u - 1].append((w, v - 1))
	adj[v - 1].append((w, u - 1))
pq = []
heappush(pq, (0, 0))
while pq:
	(du, u) = heappop(pq)
	for (w, v) in adj[u]:
		if d[v] > d[u] + w:
			(d[v], p[v]) = (d[u] + w, u)
			heappush(pq, (d[v], v))
if d[n - 1] == oo:
	print(-1)
else:
	path = []
	v = n - 1
	while v != -1:
		path.append(v + 1)
		v = p[v]
	path.reverse()
	print(' '.join(map(str, path)))


import collections
import heapq
(n, m) = [int(x) for x in input().split()]
G = collections.defaultdict(list)
for i in range(m):
	(l, r, w) = [int(x) for x in input().split()]
	G[l].append((r, w))
	G[r].append((l, w))

def dijkstra(s):
	d = [float('inf') for _ in range(n + 1)]
	pre = [-1 for _ in range(n + 1)]
	d[s] = 0
	hq = [(0, s, -1)]
	while hq:
		(v, p, q) = heapq.heappop(hq)
		if d[p] < v:
			continue
		pre[p] = q
		for (e, w) in G[p]:
			if d[e] > d[p] + w:
				d[e] = d[p] + w
				heapq.heappush(hq, (d[e], e, p))
	return (d, pre)
(d, pre) = dijkstra(1)
ans = []
pp = n
while pp != -1:
	ans.append(pp)
	pp = pre[pp]
if ans[-1] != 1:
	print(-1)
else:
	print(' '.join([str(i) for i in ans[::-1]]))


import heapq
R = lambda : map(int, input().split())
(n, m) = R()
edges = [list() for _ in range(n)]
prev = [-1] * n
dist = [float('inf')] * (n - 1) + [0]
priority_queue = [(0, n - 1)]
unvisited = set(range(n))
for _ in range(m):
	(a, b, w) = R()
	edges[a - 1].append((b - 1, w))
	edges[b - 1].append((a - 1, w))
while priority_queue:
	(current_dist, current_node) = heapq.heappop(priority_queue)
	if not current_node:
		break
	if current_node in unvisited:
		unvisited.remove(current_node)
		for (node, weight) in edges[current_node]:
			alt = current_dist + weight
			if alt < dist[node]:
				(dist[node], prev[node]) = (alt, current_node)
			heapq.heappush(priority_queue, (alt, node))
ptr = 0
path = list()
while ptr != -1:
	path.append(ptr)
	ptr = prev[ptr]
if path[-1] != n - 1:
	print(-1)
else:
	print(' '.join([str(p + 1) for p in path]))


import heapq
INF = 10 ** 13

def dijk(st, d, p, g):
	q = [(d[st], st)]
	while q:
		(ln, v) = heapq.heappop(q)
		if ln > d[v]:
			continue
		for (to, w) in g[v]:
			if d[to] > ln + w:
				d[to] = ln + w
				p[to] = v
				heapq.heappush(q, (d[to], to))

def main():
	(n, m) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	for _ in range(m):
		(u, v, w) = map(int, input().split())
		g[u].append((v, w))
		g[v].append((u, w))
	d = [INF] * (n + 1)
	p = [-1] * (n + 1)
	d[1] = 0
	dijk(1, d, p, g)
	if d[n] == INF:
		print(-1)
		exit()
	path = []
	while n != -1:
		path.append(n)
		n = p[n]
	path.reverse()
	print(' '.join(map(str, path)))
main()


(n, m) = [int(x) for x in input().split()]
edges = [[] for _ in range(n)]
dist = [int(1000000000000.0)] * n
prev = [-1] * n
for i in range(m):
	(a, b, w) = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	edges[a].append((b, w))
	edges[b].append((a, w))
import heapq
q = []
heapq.heappush(q, (0, 0))
dist[0] = 0
while len(q) > 0:
	(dst, curr) = heapq.heappop(q)
	if dst > dist[curr]:
		continue
	if curr == n - 1:
		break
	for (nxt, weight) in edges[curr]:
		ncost = dst + weight
		if ncost < dist[nxt]:
			dist[nxt] = ncost
			heapq.heappush(q, (ncost, nxt))
			prev[nxt] = curr
if prev[n - 1] == -1:
	print(-1)
else:
	res = [n]
	curr = n - 1
	while prev[curr] >= 0:
		res.append(prev[curr] + 1)
		curr = prev[curr]
	res.reverse()
	print(*res)


from collections import defaultdict
import heapq
I = 1 << 60
(n, m) = map(int, input().split())
graph = defaultdict(list)
dist = [0] + [I] * n
path = [-1] * n
minheap = [(0, 0)]
for _ in range(m):
	(a, b, w) = map(int, input().split())
	graph[a - 1].append((w, b - 1))
	graph[b - 1].append((w, a - 1))
while minheap:
	u = heapq.heappop(minheap)[1]
	for node in graph[u]:
		(temp, data) = (dist[u] + node[0], node[1])
		if temp < dist[data]:
			(dist[data], path[data]) = (temp, u)
			heapq.heappush(minheap, (dist[data], data))
if dist[n - 1] == I:
	print(-1)
else:
	(x, y) = (n - 1, [])
	while x != -1:
		y += [x + 1]
		x = path[x]
	y.reverse()
	print(' '.join(map(str, y)))


import heapq
from heapq import *
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
	(x, y, w) = map(int, input().split())
	if x != y:
		graph[x].append((y, w))
		graph[y].append((x, w))
path = [i for i in range(n + 1)]
dis = [float('inf')] * (n + 1)
que = [(0, 1)]
while que:
	(dcur, cur) = heappop(que)
	for (v, w) in graph[cur]:
		if dcur + w < dis[v]:
			dis[v] = dcur + w
			path[v] = cur
			heappush(que, (dis[v], v))
l = [n]
x = n
if dis[n] != float('inf'):
	while x != 1:
		x = path[x]
		l.append(x)
	print(*l[::-1])
else:
	print(-1)


from heapq import *
import random
m = 10
n = 10
(m, n) = map(int, input().split())
g = [[] for _ in range(m)]
for i in range(n):
	(src, dst, dist) = map(int, input().split())
	g[src - 1] += [(dist, dst - 1)]
	g[dst - 1] += [(dist, src - 1)]
INF = 10 ** 12
d = [0] + [INF] * m
path = [-1] * m
updatePointList = [(0, 0)]
while updatePointList:
	src = heappop(updatePointList)[1]
	for edge in g[src]:
		dist = edge[0] + d[src]
		dst = edge[1]
		if dist < d[dst]:
			d[dst] = dist
			path[dst] = src
			heappush(updatePointList, (d[dst], dst))
if d[m - 1] == INF:
	print('-1')
else:
	lastPoint = m - 1
	ans = []
	while lastPoint != -1:
		ans += [lastPoint + 1]
		lastPoint = path[lastPoint]
	ans.reverse()
	print(' '.join(map(str, ans)))


from heapq import heappop, heappush
from collections import deque
inf = 1 << 60
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
Q = []
dist = {}
prev = {}
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append((b, c))
	G[b].append((a, c))
dist[0] = 0
heappush(Q, (dist[0], 0))
while Q:
	(d, v) = heappop(Q)
	if d != dist[v]:
		continue
	for (u, w) in G[v]:
		curr_dist = d + w
		if dist.get(u, inf) > curr_dist:
			dist[u] = curr_dist
			prev[u] = v
			heappush(Q, (curr_dist, u))
if n - 1 not in dist:
	print(-1)
	exit(0)
d = deque([n])
curr = n - 1
while curr:
	curr = prev[curr]
	d.appendleft(curr + 1)
print(*d)


import sys, heapq

def dijkstra(n, graph, start):
	(dist, parent) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, u) = heapq.heappop(queue)
		if path_len == dist[u]:
			for (v, w) in graph[u]:
				if w + path_len < dist[v]:
					(dist[v], parent[v]) = (w + path_len, u)
					heapq.heappush(queue, (w + path_len, v))
	return (dist, parent)

def main():
	input = sys.stdin.readline
	(V, E) = map(int, input().split())
	graph = {i: [] for i in range(V)}
	for _ in range(E):
		(u, v, w) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		graph[u].append((v, w))
		graph[v].append((u, w))
	(dist, parent) = dijkstra(V, graph, 0)
	if dist[V - 1] == float('inf'):
		sys.stdout.write(str(-1) + '\n')
	else:
		ans = []
		x = V - 1
		while parent[x] != -1:
			ans.append(x + 1)
			x = parent[x]
		ans.append(1)
		print(*ans[::-1])
main()


from heapq import *
INF = 1e+16
(n, m) = map(int, input().split())
grafo = [[] for _ in range(n)]
distancia = [0] + [INF] * n
vertice_anterior = [-1] * n
q = [(0, 0)]
for i in range(m):
	(a, b, w) = map(int, input().split())
	grafo[a - 1] += [(w, b - 1)]
	grafo[b - 1] += [(w, a - 1)]
while q:
	a = heappop(q)[1]
	for adj in grafo[a]:
		(w, b) = (distancia[a] + adj[0], adj[1])
		if w < distancia[b]:
			(distancia[b], vertice_anterior[b]) = (w, a)
			heappush(q, (distancia[b], b))
if distancia[n - 1] == INF:
	print(-1)
else:
	(x, y) = (n - 1, [])
	while x != -1:
		y += [x + 1]
		x = vertice_anterior[x]
	y.reverse()
	print(' '.join(map(str, y)))


from heapq import heapify, heappop, heappush
(n, m) = map(int, input().split())
weight = {}
adj = [[] for i in range(n + 1)]
dist = [float('inf')] * (1 + n)
for _ in range(m):
	(a, b, w) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
	weight[a, b] = w
	weight[b, a] = w

def backtrack():
	res = [n]
	q = [n]
	while q:
		u = q.pop()
		for v in adj[u]:
			if dist[v] + weight[v, u] == dist[u]:
				q.append(v)
				res.append(v)
				break
	res.reverse()
	return res

def dijkstra():
	dist[1] = 0
	li = [(0, 1)]
	heapify(li)
	while li:
		pura = heappop(li)
		(d, u) = pura
		for i in range(len(adj[u])):
			v = adj[u][i]
			if dist[v] > dist[u] + weight[u, v]:
				dist[v] = dist[u] + weight[u, v]
				heappush(li, (dist[v], v))
	if dist[n] == float('inf'):
		return [-1]
	return backtrack()
print(*dijkstra())


from heapq import *
INF = 1 << 64
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
d = [INF for i in range(n)]
d[0] = 0
q = [(0, 0)]
p = [-1 for i in range(n)]
for i in range(m):
	(a, b, w) = map(int, input().split())
	g[a - 1].append((b - 1, w))
	g[b - 1].append((a - 1, w))
while q:
	v = heappop(q)[1]
	for (x, len) in g[v]:
		if d[x] > d[v] + len:
			d[x] = d[v] + len
			heappush(q, (d[x], x))
			p[x] = v
if d[n - 1] > INF / 2:
	print(-1)
else:
	ans = []
	v = n - 1
	while v != -1:
		ans.append(str(v + 1))
		v = p[v]
	print(' '.join(ans[::-1]))


from heapq import heappop, heappush

def dijkstra(graph, start):
	n = len(graph)
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	graph[a - 1].append((b - 1, c))
	graph[b - 1].append((a - 1, c))
(dl, pl) = dijkstra(graph, 0)
if dl[n - 1] == float('inf'):
	print(-1)
else:
	temp = n - 1
	path = [n]
	while pl[temp] != -1:
		path.append(pl[temp] + 1)
		temp = pl[temp]
	print(*path[::-1])


from heapq import heapify, heappush, heappop
from dataclasses import dataclass, field
from typing import Any
from itertools import count

@dataclass(order=True)
class Node:
	priority: Any = field(compare=True)
	task: Any = field(compare=False)

class PriorityHeap:

	def __init__(self, lst):
		self.counter = count()
		self.size = 0
		self.entry_finder = {}
		self.heap = list()
		for (task, pri) in lst.items():
			node = self.create_node(task, pri)
			self.entry_finder[task] = node
			self.heap.append(node)
		heapify(self.heap)
		self.size = len(self.heap)

	def create_node(self, task, priority):
		return Node((priority, next(self.counter)), task)

	def add_task(self, task, priority):
		if task in self.entry_finder:
			self.remove_task(task)
		node = self.create_node(task, priority)
		self.entry_finder[task] = node
		heappush(self.heap, node)
		self.size += 1

	def remove_task(self, task):
		entry = self.entry_finder.pop(task)
		entry.task = None
		self.size -= 1

	def pop_task(self):
		while self.size > 0:
			node = heappop(self.heap)
			if node.task is not None:
				del self.entry_finder[node.task]
				self.size -= 1
				return node.task
		self.heap = list()
		raise KeyError('pop from an empty priority queue')

	def __len__(self):
		return self.size

def dijkstra(graph, vertices, source, dest):
	distance = {source: 0}
	ph = PriorityHeap(distance)
	parent = dict()
	while len(ph) != 0:
		vertex = ph.pop_task()
		for (v, w) in graph[vertex]:
			if distance.get(v, float('inf')) > distance[vertex] + w:
				distance[v] = distance[vertex] + w
				ph.add_task(v, distance[v])
				parent[v] = vertex
		if vertex == dest:
			return (distance, parent)
	return (distance, parent)
(n, m) = (int(x) for x in input().split())
vertices = range(1, n + 1)
graph = {}
for v in vertices:
	graph[v] = list()
for _ in range(m):
	(a, b, w) = (int(x) for x in input().split())
	graph[a].append((b, w))
	graph[b].append((a, w))
(distance, parent) = dijkstra(graph, vertices, 1, n)
if n not in parent:
	print(-1)
else:
	ans = []
	cur = n
	while cur != 1:
		ans.append(str(cur))
		cur = parent[cur]
	ans.append(str(1))
	print(' '.join(reversed(ans)))


import heapq

class WeightedGraph:

	def __init__(self, n):
		self.adj_list = [[] for x in range(n)]
		self.V = n
		self.E = 0

	def add_edge(self, u, v, weight):
		self.adj_list[u].append((v, weight))
		self.adj_list[v].append((u, weight))
		self.E += 1

	def neighbors(self, v):
		return self.adj_list[v]

	def dijkstra(self, u, v):
		seen = [False] * self.V
		mh = [(0, u)]
		d = [float('inf') for x in range(self.V)]
		d[u] = 0
		prev_node = [-1] * self.V
		while len(mh) > 0:
			(cost, node) = heapq.heappop(mh)
			if not seen[node]:
				seen[node] = True
				if node == v:
					return (cost, prev_node)
				for (w, weight) in self.adj_list[node]:
					if not seen[w]:
						g = weight + cost
						if d[w] > g:
							prev_node[w] = node
							d[w] = g
							item = (d[w], w)
							heapq.heappush(mh, item)
		return None

def solve():
	(n, m) = tuple(map(int, input().split()))
	G = WeightedGraph(n)
	for x in range(m):
		line = input().split()
		u = int(line[0])
		v = int(line[1])
		w = int(line[2])
		G.add_edge(u - 1, v - 1, w)
	res = G.dijkstra(0, n - 1)
	if not res:
		print('-1')
	else:
		prevs = res[1]
		idx = n - 1
		spath = [n]
		while True:
			spath.append(prevs[idx] + 1)
			if prevs[idx] == 0:
				break
			idx = prevs[idx]
		for x in reversed(spath):
			print(x, end=' ')
solve()


import sys, heapq
(n, m) = [int(x) for x in sys.stdin.readline().split()]
e = {}
for i in range(1, n + 1):
	e[i] = {}
for i in range(m):
	(v, u, w) = [int(x) for x in sys.stdin.readline().split()]
	if not u in e[v] or e[v][u] > w:
		e[v][u] = w
	if not v in e[u] or e[u][v] > w:
		e[u][v] = w
INF = 1000000000000
pq = []
heapq.heappush(pq, (0, n))
prev = [-1] * (n + 1)
dist = [INF] * (n + 1)
vis = [False] * (n + 1)
dist[n] = 0
while len(pq) > 0:
	(d, v) = heapq.heappop(pq)
	if vis[v]:
		continue
	vis[v] = True
	if v == 1:
		break
	for u in e[v]:
		alt = dist[v] + e[v][u]
		if alt < dist[u]:
			dist[u] = alt
			prev[u] = v
			heapq.heappush(pq, (alt, u))
p = 1
path = []
while p != -1:
	path.append(str(p))
	p = prev[p]
if path[-1] != str(n):
	print(-1)
else:
	print(' '.join(path))


from heapq import heappop, heappush
from sys import stdin

def make_graph(m):
	graph = {}
	for i in range(m):
		s = input()
		(u, v, w) = (int(t) for t in s.split())
		if u not in graph:
			graph[u] = {}
		if v not in graph:
			graph[v] = {}
		graph[u][v] = w
		graph[v][u] = w
	return graph

class vertex_type:

	def __init__(self, vertex):
		self.vertex = vertex

	def __lt__(self, rhs):
		return vertex_type.distance[self.vertex] < vertex_type.distance[rhs.vertex]

def find_path(graph, b, e):
	queue = []
	successor = {e: e}
	vertex_type.distance = {e: 0}
	heappush(queue, vertex_type(e))
	while queue:
		u = heappop(queue).vertex
		if u == b:
			path = [b]
			while u != e:
				u = successor[u]
				path.append(u)
			return path
		if u not in graph:
			continue
		for v in graph[u]:
			distance = vertex_type.distance[u] + graph[u][v]
			if v not in vertex_type.distance or distance < vertex_type.distance[v]:
				successor[v] = u
				vertex_type.distance[v] = distance
				heappush(queue, vertex_type(v))
	return [-1]

def test_case(n, m):
	b = 1
	e = n
	graph = make_graph(m)
	path = find_path(graph, b, e)
	print(' '.join((str(v) for v in path)))

def main():
	for s in stdin:
		(n, m) = (int(t) for t in s.split())
		test_case(n, m)
main()


import math
from collections import deque
import os
import sys
import heapq
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
(n, m) = invr()
d = {}
v = [0] * n
for i in range(1, n + 1):
	d[i] = []
for i in range(m):
	(a, b, w) = invr()
	d[a].append([b, w])
	d[b].append([a, w])
out = {}
c = {}
c[1] = 0
for i in range(2, n + 1):
	c[i] = float('inf')
queue = deque()
x = []
heapq.heappush(x, (0, 1, -1))
prev = -1
while True:
	a = heapq.heappop(x)
	s = a[1]
	if v[s - 1] == 1:
		continue
	v[s - 1] = 1
	c[s] = a[0]
	out[s] = a[2]
	if s == n:
		break
	for i in d[s]:
		if not v[i[0] - 1]:
			if a[0] + i[1] < c[i[0]]:
				heapq.heappush(x, (a[0] + i[1], i[0], s))
	if len(x) == 0:
		print(-1)
		exit()
a = []
x = n
while out[x] != -1:
	a.append(x)
	x = out[x]
a.append(1)
a.reverse()
print(*a)


def main():
	from heapq import heappush, heappop
	(n, m) = map(int, input().split())
	g = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b, w) = map(int, input().split())
		g[a].append((b, w))
		g[b].append((a, w))
	(h, tt, parent) = ([(0, 1)], [2 ** 40] * (n + 1), [0] * (n + 1))
	while h:
		(d, v) = heappop(h)
		for (u, w) in g[v]:
			w += d
			if tt[u] > w:
				parent[u] = v
				tt[u] = w
				heappush(h, (w, u))
	if not parent[n]:
		print(-1)
		return
	(res, v) = ([n], n)
	while v != 1:
		v = parent[v]
		res.append(v)
	print(' '.join(map(str, reversed(res))))
main()


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List
(N, M) = map(int, input().split())
g = collections.defaultdict(dict)
for _ in range(M):
	(u, v, w) = map(int, input().split())
	if u == v:
		continue
	if v not in g[u]:
		g[u][v] = w
	else:
		g[u][v] = min(g[u][v], w)
	if u not in g[v]:
		g[v][u] = w
	else:
		g[v][u] = min(g[v][u], w)
dists = [float('inf') for _ in range(N + 1)]
pre = [-1 for _ in range(N + 1)]
q = [(w, v) for (v, w) in g[1].items()]
for (w, v) in q:
	pre[v] = 1
	dists[v] = w
dists[1] = 0
heapq.heapify(q)
while q:
	(d, u) = heapq.heappop(q)
	for (v, w) in g[u].items():
		nd = d + w
		if nd < dists[v]:
			dists[v] = nd
			pre[v] = u
			heapq.heappush(q, (nd, v))
if dists[N] < float('inf'):
	ans = []
	u = N
	while u > 0:
		ans.append(u)
		u = pre[u]
	print(' '.join(map(str, ans[::-1])))
else:
	print(-1)


import heapq, sys
(n, m) = map(int, input().split())
adj = dict()
for i in range(1, n + 1):
	adj[i] = dict()
for i in range(m):
	(a, b, c) = map(int, input().split())
	if not a in adj[b] or adj[a][b] > c:
		adj[b][a] = c
	if not b in adj[a] or adj[b][a] > c:
		adj[a][b] = c
INF = 10000000000000
prev = [-1] * (n + 1)
visited = [0] * (n + 1)
dist = [INF] * (n + 1)
pq = []
heapq.heappush(pq, (0, 1))
dist[1] = 0
while len(pq) > 0:
	(c, u) = heapq.heappop(pq)
	if visited[u]:
		continue
	visited[u] = True
	if u == n:
		break
	for v in adj[u]:
		alt = dist[u] + adj[u][v]
		if alt < dist[v]:
			dist[v] = alt
			prev[v] = u
			heapq.heappush(pq, (alt, v))
st = [0] * (n + 3)
k = n - 1
i = n
while i != -1:
	st[k] = i
	k -= 1
	i = prev[i]
if st[k + 1] != 1:
	print(-1)
	sys.exit()
for i in range(k + 1, n, 1):
	print(st[i], end=' ')


from heapq import heappop, heappush
(n, m) = [int(i) for i in input().split()]
graph = [[] for _ in range(n)]
shortest = [0] + [float('inf')] * n
for i in range(m):
	(a, b, w) = map(int, input().split())
	graph[a - 1] += [(w, b - 1)]
	graph[b - 1] += [(w, a - 1)]
search_queue = [(0, 0)]
closest_parent = [n + 1] * n
while search_queue:
	a = heappop(search_queue)[1]
	for e in graph[a]:
		(w, b) = (shortest[a] + e[0], e[1])
		if w < shortest[b]:
			(shortest[b], closest_parent[b]) = (w, a)
			heappush(search_queue, (shortest[b], b))
if shortest[n - 1] == float('inf'):
	print(-1)
else:
	(next_p, shortest_p) = (n - 1, [])
	while next_p != n + 1:
		shortest_p += [next_p + 1]
		next_p = closest_parent[next_p]
	shortest_p.reverse()
	print(' '.join([str(i) for i in shortest_p]))


from collections import defaultdict
import heapq
MAX = float('inf')
(n, m) = map(int, input().split(' '))
graph = defaultdict(set)
for _ in range(m):
	(s, d, w) = map(int, input().split(' '))
	graph[s].add((d, w))
	graph[d].add((s, w))
pq = [(0, 1, None)]
parents = {}
discovered = set()
distance = [MAX] * (n + 1)
distance[1] = 0
while len(pq) != 0:
	(_, u, parent) = heapq.heappop(pq)
	if u in discovered:
		continue
	discovered.add(u)
	parents[u] = parent
	if u == n:
		node = n
		path = []
		while node != None:
			path.append(node)
			node = parents[node]
		path.reverse()
		print(' '.join(map(str, path)))
		exit()
	for (v, w) in graph[u]:
		if distance[u] + w < distance[v]:
			distance[v] = distance[u] + w
			heapq.heappush(pq, (distance[v], v, u))
print(-1)


from heapq import *
I = 1 << 60
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
d = [0] + [I] * n
p = [-1] * n
q = [(0, 0)]
for i in range(m):
	(a, b, w) = map(int, input().split())
	g[a - 1] += [(w, b - 1)]
	g[b - 1] += [(w, a - 1)]
while q:
	a = heappop(q)[1]
	for e in g[a]:
		(w, b) = (d[a] + e[0], e[1])
		if w < d[b]:
			(d[b], p[b]) = (w, a)
			heappush(q, (d[b], b))
if d[n - 1] == I:
	print(-1)
else:
	(x, y) = (n - 1, [])
	while x != -1:
		y += [x + 1]
		x = p[x]
	y.reverse()
	print(' '.join(map(str, y)))


from heapq import heappush, heappop

def add_edge_to_graph(graph, U, V, W):
	if U in graph:
		graph[U].append((W, V))
	else:
		graph[U] = [(W, V)]

def construct_path(parent_dict, n):
	if n not in parent_dict:
		return None
	parent = n
	path = []
	while parent != None:
		path.append(parent)
		parent = parent_dict[parent]
	return reversed(path)
(n, m) = map(int, input().split())
graph = {}
for _ in range(m):
	(U, V, weight) = map(int, input().split())
	add_edge_to_graph(graph, U, V, weight)
	add_edge_to_graph(graph, V, U, weight)
visited = set()
pri_q = [(0, 1, None)]
parent_dict = {}
if 1 in graph and n in graph:
	while pri_q:
		(weight, node, parent) = heappop(pri_q)
		if node in visited:
			continue
		visited.add(node)
		parent_dict[node] = parent
		if node == n:
			break
		children = graph[node]
		for child in children:
			if child[1] not in visited:
				parent = node
				new_weight = child[0] + weight
				heappush(pri_q, (new_weight, child[1], node))
final_path = construct_path(parent_dict, n)
if final_path == None:
	print(-1)
else:
	print(' '.join(map(str, final_path)))


from heapq import heappush, heappop
infinity = 99999999999999
(vertice, edge) = map(int, input().split())
graph = [[] for _ in range(vertice)]
d = [0] + [infinity] * vertice
p = [-1] * vertice
q = [(0, 0)]
for _ in range(edge):
	(u, v, weight) = map(int, input().split())
	graph[u - 1] += [(weight, v - 1)]
	graph[v - 1] += [(weight, u - 1)]
while q:
	u = heappop(q)[1]
	for e in graph[u]:
		(t, v) = (d[u] + e[0], e[1])
		if t < d[v]:
			(d[v], p[v]) = (t, u)
			heappush(q, (d[v], v))
if d[vertice - 1] == infinity:
	print(-1)
else:
	(x, a) = (vertice - 1, [])
	while x != -1:
		a += [x + 1]
		x = p[x]
	a.reverse()
	print(' '.join(map(str, a)))


from heapq import heappop, heappush

def i_in():
	return map(int, input().split())
(nodes, edges) = i_in()
graph = [[] for x in range(nodes)]
for x in range(edges):
	(left, right, cost) = i_in()
	left -= 1
	right -= 1
	graph[left].append((cost, right))
	graph[right].append((cost, left))
visited = [False for x in range(nodes)]
previous = [-1 for x in range(nodes)]
pq = [(0, 0, -1)]
found = False
while pq:
	(path_cost, node, prev) = heappop(pq)
	if visited[node]:
		continue
	visited[node] = True
	previous[node] = prev
	if node == nodes - 1:
		found = True
		break
	for (cost, adj) in graph[node]:
		if not visited[adj]:
			heappush(pq, (path_cost + cost, adj, node))
if not found:
	print(-1)
	quit()
path = []
current = nodes - 1
while current != -1:
	path.append(str(current + 1))
	current = previous[current]
path.reverse()
print(' '.join(path))


import heapq
INF = 1 << 60

class Graph:

	def __init__(self, n):
		self.neighbours = [[] for x in range(n + 1)]

	def addEdge(self, u, v, cost):
		self.neighbours[u].append((v, cost))
		self.neighbours[v].append((u, cost))

	def dijkstra(self, s, d, n):
		parent = {s: None}
		distanceFromS = [INF for x in range(n + 1)]
		distanceFromS[s] = 0
		visited = [False for x in range(n + 1)]
		remaining = [(0, s)]
		while remaining:
			(minDist, minNode) = heapq.heappop(remaining)
			if not visited[minNode]:
				visited[minNode] = True
				if visited[d]:
					return parent
				for (v, length) in self.neighbours[minNode]:
					if not visited[v]:
						greedyScore = minDist + length
						if greedyScore < distanceFromS[v]:
							distanceFromS[v] = greedyScore
							parent[v] = minNode
							heapq.heappush(remaining, (greedyScore, v))
		return parent
(n, m) = [int(x) for x in input().split()]
g = Graph(n)
for i in range(m):
	(u, v, cost) = [int(x) for x in input().split()]
	g.addEdge(u, v, cost)
path = g.dijkstra(1, n, n)
if n not in path:
	print(-1)
else:
	ans = []
	current = n
	while current != None:
		ans.append(current)
		current = path[current]
	print(*ans[::-1])


from collections import defaultdict
import sys
from heapq import *

def dijakstra(starting, ending, graph, distance):
	distance[starting] = 0
	q = [(distance[starting], starting)]
	parent = {i: -1 for i in range(1, n + 1)}
	seen = set()
	while q:
		(now_dis, now_node) = heappop(q)
		if now_node in seen:
			continue
		seen.add(now_node)
		for neighbour in graph[now_node]:
			if distance[now_node] + neighbour[1] < distance[neighbour[0]]:
				parent[neighbour[0]] = now_node
				distance[neighbour[0]] = distance[now_node] + neighbour[1]
				heappush(q, (distance[neighbour[0]], neighbour[0]))
	return (distance, parent)

def shortestReach(n, edges, s):
	distance = [-1] * (n + 1)
	distance[s] = 0
	q = [(distance[s], s)]
	parent = {i: -1 for i in range(1, n + 1)}
	visited = [False] * (n + 1)
	while q:
		(now_dis, now_node) = heappop(q)
		if visited[now_node] == True:
			continue
		visited[now_node] = True
		for neighbour in edges[now_node]:
			(curr_weight, curr_node) = (neighbour[1], neighbour[0])
			if distance[curr_node] == -1:
				parent[curr_node] = now_node
				distance[curr_node] = distance[now_node] + curr_weight
				heappush(q, (distance[curr_node], curr_node))
			elif distance[now_node] + curr_weight < distance[curr_node]:
				parent[curr_node] = now_node
				distance[curr_node] = distance[now_node] + curr_weight
				heappush(q, (distance[curr_node], curr_node))
	return parent

def backtrace(parent, start, end):
	path = [end]
	while path[-1] != start and path[-1] > 0:
		path.append(parent[path[-1]])
	path.reverse()
	return path
(n, m) = map(int, input().split())
graph = defaultdict(list)
distance = [sys.maxsize for _ in range(n + 1)]
for _ in range(m):
	(u, v, w) = map(int, input().split())
	graph[u].append([v, w])
	graph[v].append([u, w])
parent = shortestReach(n, graph, 1)
if parent[n] == -1:
	print(-1)
else:
	print(*backtrace(parent, 1, n))


from heapq import heappush, heappop

def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
(n, m) = MAP()
g = [[] for i in range(n)]
for i in range(m):
	(u, v, w) = MAP()
	u -= 1
	v -= 1
	g[u].append([v, w])
	g[v].append([u, w])
cost = [2 ** 40 + 9] * n
parents = [None] * n
q = [(0, 0)]
while q:
	(s1, s2) = heappop(q)
	for (u, w) in g[s2]:
		if cost[u] > s1 + w:
			parents[u] = s2
			cost[u] = s1 + w
			heappush(q, (cost[u], u))
if parents[n - 1] == None:
	print(-1)
	exit(0)
ans = [n]
x = n - 1
while x != 0:
	x = parents[x]
	ans.append(x + 1)
print(*ans[::-1])


from heapq import heappop, heappush
from sys import stdin

def make_graph(m):
	graph = {}
	for i in range(m):
		s = input()
		(u, v, w) = (int(t) for t in s.split())
		if u not in graph:
			graph[u] = {}
		if v not in graph:
			graph[v] = {}
		if v not in graph[u]:
			graph[u][v] = w
			graph[v][u] = w
		else:
			graph[u][v] = min(graph[u][v], w)
			graph[v][u] = min(graph[v][u], w)
	return graph

def search(graph, b, e):
	queue = []
	successors = {e: e}
	weights = {e: 0}
	heappush(queue, (0, e))
	while queue:
		(w, u) = heappop(queue)
		if u == b:
			path = [b]
			while b != e:
				b = successors[b]
				path.append(b)
			return path
		if u not in graph:
			continue
		for v in graph[u]:
			cw = weights[u] + graph[u][v]
			if v not in weights or cw < weights[v]:
				heappush(queue, (cw, v))
				successors[v] = u
				weights[v] = cw
	return [-1]

def test_case(n, m):
	b = 1
	e = n
	graph = make_graph(m)
	path = search(graph, b, e)
	print(' '.join((str(v) for v in path)))

def main():
	for s in stdin:
		(n, m) = (int(t) for t in s.split())
		test_case(n, m)
main()


import heapq
import pdb

class priority_queue:

	def __init__(self):
		self.pq = []

	def push(self, item):
		heapq.heappush(self.pq, item)

	def pop(self):
		return heapq.heappop(self.pq)

	def __bool__(self):
		return bool(len(self.pq))

class graph:

	def __init__(self, n):
		self.n = n
		self.adj = [[] for _ in range(n)]

	def adde(self, u, v, w):
		self.adj[u].append([v, w])
		self.adj[v].append([u, w])

	def dijkstra(self, s):
		dist = [float('inf')] * self.n
		pred = [-1] * self.n
		visited = [False] * self.n
		dist[s] = 0
		remaining = priority_queue()
		remaining.push((0, s))
		while remaining:
			(d, u) = remaining.pop()
			if visited[u]:
				continue
			visited[u] = True
			for (v, w) in self.adj[u]:
				new_d = d + w
				if new_d < dist[v]:
					dist[v] = new_d
					pred[v] = u
					remaining.push((new_d, v))
		return (dist, pred)
(n, m) = [int(x) for x in input().split()]
g = graph(n + 1)
for _ in range(m):
	(a, b, w) = [int(x) for x in input().split()]
	g.adde(a, b, w)
(dist, pred) = g.dijkstra(1)
path = [n]
while True:
	pnode = path[-1]
	nnode = pred[pnode]
	if nnode == -1:
		if pnode != 1:
			path = [-1]
		break
	path.append(nnode)
print(' '.join(reversed([str(x) for x in path])))


import heapq as h

def dijkstra(G, start):
	n = len(G)
	visited = [False] * n
	weights = [float('inf')] * n
	path = [None] * n
	queue = []
	weights[start] = 0
	h.heappush(queue, (0, start))
	while len(queue) > 0:
		(tezina, cvor) = h.heappop(queue)
		visited[cvor] = True
		for (v, w) in G[cvor]:
			if not visited[v]:
				ukupnaTezina = tezina + w
				if ukupnaTezina < weights[v]:
					weights[v] = ukupnaTezina
					path[v] = cvor
					h.heappush(queue, (ukupnaTezina, v))
	return path
(n, m) = map(int, input().split())
l = [[] for i in range(n)]
for i in range(m):
	(od, do, t) = map(int, input().split())
	l[do - 1].append((od - 1, t))
	l[od - 1].append((do - 1, t))
m = dijkstra(l, 0)

def put(m, n):
	sada = m[n - 1]
	mat = [str(n)]
	while True:
		if sada is None:
			break
		mat.append(str(sada + 1))
		sada = m[sada]
	if m[n - 1] is None:
		return -1
	else:
		return ' '.join(mat[::-1])
print(put(m, n))


from heapq import *
MAX_N = 100005
inf = 1000000000007
dist = [inf for _ in range(MAX_N)]
trace = [-1 for _ in range(MAX_N)]
adj = [[] for _ in range(MAX_N)]

def Dijkstra(start):
	pq = []
	dist[start] = 0
	heappush(pq, (0, 1))
	while pq:
		(distance, u) = heappop(pq)
		if distance != dist[u]:
			continue
		if u == n:
			break
		for neighbor in adj[u]:
			(v, w) = neighbor
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heappush(pq, (dist[v], v))
				trace[v] = u

def findPath():
	if dist[n] == inf:
		print(-1)
		return
	u = n
	res = []
	while u != -1:
		res.append(u)
		u = trace[u]
	for i in range(len(res) - 1, -1, -1):
		print(res[i], end=' ')
(n, m) = map(int, input().split())
for i in range(m):
	(u, v, w) = map(int, input().split())
	adj[u].append((v, w))
	adj[v].append((u, w))
Dijkstra(1)
findPath()


import bisect
(n, m) = map(int, input().split())
INF = 10 ** 11 + 1
edges = {k: [] for k in range(n)}
for i in range(m):
	(a, b, w) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	edges[a].append((b, -w))
	edges[b].append((a, -w))
distances = [0] + [-INF] * (n - 1)
distance_pairs = [(distances[k], k) for k in range(n)]
parents = [0] + [-1] * (n - 1)
distance_pairs.sort()
fixed = [False] * n
for _ in range(n - 1):
	(cur_dist, cur_node) = (0, 0)
	while fixed[cur_node]:
		(cur_dist, cur_node) = distance_pairs.pop()
	for (e_target, e_dist) in edges[cur_node]:
		if cur_dist + e_dist > distances[e_target]:
			distances[e_target] = cur_dist + e_dist
			bisect.insort(distance_pairs, (cur_dist + e_dist, e_target))
			parents[e_target] = cur_node
	fixed[cur_node] = True
if distances[-1] != -INF:
	del distance_pairs
	path = [n - 1]
	while path[-1] != 0:
		path.append(parents[path[-1]])
	print(*[k + 1 for k in path[::-1]])
else:
	print(-1)


import heapq

def dijkstra(nodes, edges):
	graph = [[]]
	for _ in range(nodes):
		graph.append([])
	for _ in range(edges):
		(a, b, length) = map(int, input().rstrip().split())
		graph[a].append((b, length))
		graph[b].append((a, length))
	paths = {}
	q = []
	q.append((0, None, 1))
	while len(q) > 0:
		(length, prev, cur) = heapq.heappop(q)
		if cur not in paths:
			paths[cur] = (prev, length)
			for (to, tolength) in graph[cur]:
				if to not in paths:
					heapq.heappush(q, (tolength + length, cur, to))
	if nodes in paths:
		path = [nodes]
		cur = paths[nodes][0]
		while cur is not None:
			path.append(cur)
			cur = paths[cur][0]
		path.reverse()
		print(' '.join(map(str, path)))
	else:
		print(-1)

def main():
	(nodes, edges) = map(int, input().rstrip().split())
	dijkstra(nodes, edges)
main()


import heapq
import sys
INF = 10000000000000000000
(N, M) = map(int, input().split())
dist = []
visit = []
h = []
stack = []
edges = {x: set() for x in range(1, N + 1)}
for i in range(0, N + 1):
	dist.append(INF)
	visit.append(False)
dist[1] = 0
visit[1] = True
heapq.heappush(h, (0, 1))
for i in range(M):
	ew = list(input().split())
	ew = [int(x) for x in ew]
	n1 = ew[0]
	n2 = ew[1]
	w = ew[2]
	edges[n1]
	edges[n1].add((n2, w))
	edges[n2].add((n1, w))
for e in edges[1]:
	n = e[0]
	w = e[1]
	dist[n] = w
	heapq.heappush(h, (w, n))
	stack.append((n, 1))
cnt = 0
while cnt < N:
	if h == []:
		break
	curr = heapq.heappop(h)
	w = curr[0]
	n1 = curr[1]
	visit[n1] == True
	for e in edges[n1]:
		n2 = e[0]
		w = e[1]
		d = dist[n1] + w
		if not visit[n2] and dist[n2] > d:
			dist[n2] = d
			heapq.heappush(h, (dist[n2], n2))
			stack.append((n2, n1))
	cnt += 1
if dist[N] == INF:
	print(-1)
else:
	next = N
	res = []
	while stack:
		out = stack.pop()
		if out[0] == next:
			res.append(next)
			next = out[1]
	res.append(1)
	res.reverse()
	for i in res:
		print(i, end=' ')


from heapq import *

def dijkstra(node, fim):
	q = []
	dist[node] = 0
	heappush(q, (0, node))
	while len(q) > 0:
		top = heappop(q)
		for vizinho in adj[top[1]]:
			if dist[vizinho[1]] > dist[top[1]] + vizinho[0]:
				dist[vizinho[1]] = dist[top[1]] + vizinho[0]
				path1['%d %d' % (dist[vizinho[1]], vizinho[1])] = '%d %d' % top
				heappush(q, (dist[vizinho[1]], vizinho[1]))
(v, a) = map(int, input().split())
adj = [[] for i in range(v + 1)]
dist = [float('inf')] * (v + 1)
path = []
path1 = {}
for i in range(a):
	(a, b, p) = map(int, input().split())
	adj[a].append((p, b))
	adj[b].append((p, a))
dijkstra(1, v)
pilha = []
if dist[v] == float('inf'):
	print(-1)
else:
	nome = '%d %d' % (dist[v], v)
	s = path1[nome]
	while s:
		pilha.append(nome.split()[1])
		nome = s
		if nome in path1:
			s = path1[s]
		else:
			pilha.append(nome.split()[1])
			break
	for i in range(len(pilha) - 1, -1, -1):
		if i == 0:
			print(pilha[i])
		else:
			print(pilha[i], end=' ')


from collections import deque as dq
import heapq as hq
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	g[a - 1].append((b - 1, c))
	g[b - 1].append((a - 1, c))
MAX = 10 ** 11
nodescost = [MAX] * n
nodescost[0] = 0
L = []
A = [-1] * (n + 1)
hq.heappush(L, (0, 0))
while len(L) != 0:
	v = hq.heappop(L)
	for x in g[v[1]]:
		if v[0] + x[1] <= nodescost[x[0]]:
			nodescost[x[0]] = v[0] + x[1]
			hq.heappush(L, (nodescost[x[0]], x[0]))
			A[x[0] + 1] = v[1] + 1
ans = [n]
while A[ans[-1]] != -1:
	ans += [A[ans[-1]]]
if A[n] != -1:
	ans.reverse()
	print(' '.join(map(str, ans)))
else:
	print(-1)


from sys import stdin
from collections import deque
from heapq import *

def main():
	first_line = stdin.readline().split(' ')
	num_vertices = int(first_line[0])
	num_edges = int(first_line[1])
	vertices = dict()
	lines = stdin.readlines()
	for line in lines:
		line = line.split(' ')
		a = int(line[0])
		b = int(line[1])
		cost = int(line[2])
		try:
			vert_a = vertices[a]
		except KeyError:
			vert_a = Vertex(a)
			vertices[a] = vert_a
		try:
			vert_b = vertices[b]
		except KeyError:
			vert_b = Vertex(b)
			vertices[b] = vert_b
		vert_a.edges.append(Edge(vert_a, vert_b, cost))
		vert_b.edges.append(Edge(vert_b, vert_a, cost))
	try:
		goal = vertices[num_vertices]
	except KeyError:
		print(-1)
		return
	heap = []
	root = vertices[1]
	heappush(heap, Edge(root, root, 0))
	while len(heap) > 0:
		cur_edge = heappop(heap)
		if cur_edge.to_vertex == goal:
			path = deque([cur_edge.to_vertex.name])
			parent_vertex = cur_edge.parent
			while parent_vertex != root:
				path.appendleft(parent_vertex.name)
				parent_vertex = parent_vertex.parent
			path.appendleft(root.name)
			print(' '.join((str(name) for name in path)))
			return
		if not cur_edge.to_vertex.visited:
			cur_edge.to_vertex.visited = True
			cur_edge.to_vertex.parent = cur_edge.parent
			for neighbor_edge in cur_edge.to_vertex.edges:
				if not neighbor_edge.to_vertex.visited:
					heappush(heap, Edge(neighbor_edge.parent, neighbor_edge.to_vertex, cur_edge.cost + neighbor_edge.cost))
	print(-1)

class Vertex:

	def __init__(self, name):
		self.name = name
		self.visited = False
		self.edges = []
		self.parent = None

	def __eq__(self, other):
		try:
			return self.name == other.name
		except:
			return False

	def __repr__(self):
		return 'Vertex {} with {} neighbors'.format(self.name, len(self.edges))

class Edge:

	def __init__(self, parent, to_vertex, cost):
		self.parent = parent
		self.to_vertex = to_vertex
		self.cost = cost

	def __eq__(self, other):
		try:
			return self.cost == other.cost
		except:
			return False

	def __repr__(self):
		return 'Edge from vertex {} to vertex {} with cost {}'.format(self.parent.name, self.to_vertex.name, self.cost)

	def __gt__(self, other):
		return self.cost > other.cost
main()


import heapq

class Graph:

	def __init__(self, nodes):
		self.num = nodes
		self.nodes = list((Node(x) for x in range(self.num + 1)))

	def add_edge(self, start, end, weight):
		self.nodes[start].add_edge(self.nodes[end], weight)

	def unmark_all(self):
		for node in self.nodes:
			node.unmark()

	def dijkstra(self, end):
		q = []
		q.append(self.nodes[1])
		self.nodes[1].weight = 0
		heapq.heapify(q)
		while len(q):
			current = heapq.heappop(q)
			if current is self.nodes[end]:
				return self.pathfromHere(current)
			if current.visit:
				continue
			current.mark()
			for (adj, edge_weight) in current.adjacent.items():
				if not adj.visit:
					if adj.weight > current.weight + edge_weight:
						adj.weight = current.weight + edge_weight
						adj.prev = current
					heapq.heappush(q, adj)
		return [-1]

	def pathfromHere(self, current):
		path = [current]
		while current.prev:
			path.append(current.prev)
			current = current.prev
		return reversed(path)

class Node:

	def __init__(self, x):
		self.id = x
		self.visit = False
		self.adjacent = {}
		self.weight = float('inf')
		self.prev = None

	def add_edge(self, other, weight):
		if other not in self.adjacent:
			self.adjacent[other] = weight
		elif self.adjacent[other] > weight:
			self.adjacent[other] = weight

	def __lt__(self, other):
		return self.weight < other.weight

	def __gt__(self, other):
		return self.weight > other.weight

	def __eq__(self, other):
		return self.weight == other.weight

	def __le__(self, other):
		return self.weight <= other.weight

	def __ge__(self, other):
		return self.weight >= other.weight

	def __ne__(self, other):
		return self.weight != other.weight

	def __hash__(self):
		return self.id

	def mark(self):
		self.visit = True

	def unmark(self):
		self.visit = False

	def __str__(self):
		return str(self.id)
details = list(map(int, input().split()))
n = details[0]
num_edges = details[1]
g = Graph(n)
for edge in range(num_edges):
	e = list(map(int, input().split()))
	g.add_edge(e[0], e[1], e[2])
	g.add_edge(e[1], e[0], e[2])
print(' '.join(map(str, g.dijkstra(n))))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
from decimal import Decimal
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def outa(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def dijkstra():
	pq = [[0, 1]]
	dist[1] = 0
	heapify(pq)
	while pq:
		(distance, temp) = heappop(pq)
		if dist[temp] < distance:
			continue
		for child in graph[temp]:
			new = dist[temp] + child[1]
			if new < dist[child[0]]:
				dist[child[0]] = new
				heappush(pq, [new, child[0]])
				parent[child[0]] = temp
	path()

def path():
	answer = []
	start = n
	while start:
		answer.append(start)
		start = parent[start]
	if 1 not in answer or n not in answer:
		out(-1)
		exit()
	outa(*answer[::-1])
(n, m) = sp()
graph = dd(set)
for i in range(m):
	(u, v, w) = sp()
	graph[u].add((v, w))
	graph[v].add((u, w))
parent = [0] * (n + 1)
dist = [inf] * (n + 1)
dijkstra()


from heapq import *
from sys import *
f = lambda : map(int, stdin.readline().split())
inf = 1 << 40
(n, m) = f()
k = n + 1
g = [[] for i in range(k)]
for j in range(m):
	(u, v, l) = f()
	g[u].append((v, l))
	g[v].append((u, l))
d = [inf] * k
d[1] = 0
p = [0] * k
q = [1]
while q:
	h = heappop(q)
	(v, l) = (h % k, h // k)
	if d[v] != l:
		continue
	if v == n:
		break
	for (u, l) in g[v]:
		s = d[v] + l
		if s < d[u]:
			(d[u], p[u]) = (s, v)
			heappush(q, k * s + u)
if d[n] == inf:
	print(-1)
else:
	(u, t) = (n, [])
	while u:
		t.append(u)
		u = p[u]
	t.reverse()
	print(' '.join(map(str, t)))


from sys import stdin
from heapq import heappush, heappop
from collections import deque
INF = float('inf')

def dijkstra(G, source, target):
	global distance
	n = len(G)
	visited = [0 for _ in range(n)]
	distance = [INF for _ in range(n)]
	previous = [-1 for _ in range(n)]
	distance[source] = 0
	heap = [[0, source]]
	while len(heap) and (not visited[target]):
		(du, u) = heappop(heap)
		if not visited[u]:
			visited[u] = 1
			for (dv, v) in G[u]:
				if not visited[v] and du + dv < distance[v]:
					distance[v] = du + dv
					heappush(heap, [du + dv, v])
					previous[v] = u
	return previous

def main():
	global distance
	(n, m) = map(int, stdin.readline().split())
	G = [[] for _ in range(n)]
	for _ in range(m):
		(u, v, w) = map(int, stdin.readline().split())
		G[u - 1].append([w, v - 1])
		G[v - 1].append([w, u - 1])
	ans = dijkstra(G, 0, n - 1)
	if distance[n - 1] == INF:
		print(-1)
	else:
		u = n - 1
		path = deque()
		path.append(u)
		while u != 0:
			u = ans[u]
			path.appendleft(u)
		while len(path) > 1:
			u = path.popleft()
			print(u + 1, end=' ')
		u = path.popleft()
		print(u + 1)
main()


from heapq import *

def dijkstra(d, n):
	(heap, visited, way, parents) = ([(0, 0)], set(), {0: 0}, [-1] * (n + 1))
	while heap:
		(leng, x) = heappop(heap)
		if x not in visited:
			visited.add(x)
			if x == n:
				break
			new = d[x]
			for (i, elem) in enumerate(new):
				l = new[elem]
				if elem in visited:
					continue
				item = way.get(elem)
				if item == None or leng + l < item:
					parents[elem] = x
					way[elem] = leng + l
					heappush(heap, [leng + l, elem])
	return parents
from sys import stdin
inp = lambda : stdin.readline().split()
(n, m) = map(int, inp())
d = {i: {} for i in range(n)}
for _ in range(m):
	(a, b, w) = map(int, inp())
	if a != b:
		(a, b) = (a - 1, b - 1)
		if d[a].get(b) == None:
			d[a][b] = w
			d[b][a] = w
		else:
			d[a][b] = min(d[a][b], w)
			d[b][a] = d[a][b]
p = dijkstra(d, n - 1)
if p[-1] == -1:
	print(-1)
else:
	(res, x) = ([], n - 1)
	while x > 0:
		res.append(x + 1)
		x = p[x]
	res.append(1)
	print(*res[::-1])


import heapq
inf = 100000000000.0 + 9
(m, n) = map(int, input().split())
graf = [[] for _ in range(m + 1)]
for x in range(n):
	(od, do, waga) = map(int, input().split())
	graf[od].append([do, waga])
	graf[do].append([od, waga])
kolejka = [[0, 1]]
odwiedzeni = [False for _ in range(m + 1)]
odleglosc = [inf for _ in range(m + 1)]
odleglosc[1] = 0
poprz = [0 for _ in range(m + 1)]
while kolejka:
	punkt = heapq.heappop(kolejka)
	(waga, miejsce) = (punkt[0], punkt[1])
	if odwiedzeni[miejsce]:
		continue
	odwiedzeni[miejsce] = True
	for x in graf[miejsce]:
		(sasiad, waga_s) = (x[0], x[1])
		if odwiedzeni[sasiad]:
			continue
		if odleglosc[miejsce] + waga_s < odleglosc[sasiad]:
			odleglosc[sasiad] = odleglosc[miejsce] + waga_s
			poprz[sasiad] = miejsce
			heapq.heappush(kolejka, [odleglosc[sasiad], sasiad])
trasa = [m]
while trasa[-1] != 1:
	if poprz[trasa[-1]] == 0:
		break
	else:
		trasa.append(poprz[trasa[-1]])
if trasa[-1] != 1:
	print(-1)
else:
	print(*trasa[::-1])


from heapq import *

def Dijkstra():
	(endLocation, connections) = map(int, input().split(' '))
	adjusted = endLocation + 1
	dictionary = [[] for val in range(adjusted)]
	for _ in range(connections):
		(start, end, cost) = map(int, input().split(' '))
		dictionary[start].append((end, cost))
		dictionary[end].append((start, cost))
	costs = [-1] * adjusted
	costs[1] = 0
	path = [0] * adjusted
	heap = [1]
	while heap:
		item = heappop(heap)
		(end, cost) = (item % adjusted, item // adjusted)
		if costs[end] != cost:
			continue
		for (start, cost) in dictionary[end]:
			updatedCost = costs[end] + cost
			if updatedCost < costs[start] or costs[start] == -1:
				(costs[start], path[start]) = (updatedCost, end)
				heappush(heap, adjusted * updatedCost + start)
	if costs[endLocation] == -1:
		print(-1)
	else:
		(index, toReturn) = (endLocation, [])
		while index:
			toReturn.append(index)
			index = path[index]
		toReturn.reverse()
		print(' '.join(map(str, toReturn)))
Dijkstra()


from sys import stdin, stdout
from collections import deque
from operator import itemgetter

def moore(graph, source, target):
	INF = 1 << 64
	n = len(graph)
	Q = deque([source])
	in_queue = [False for _ in range(n)]
	in_queue[source] = True
	dist = [INF for _ in range(n)]
	dist[source] = 0
	pred = list(range(n))
	while Q:
		u = Q.pop()
		in_queue[u] = False
		for (v, w_uv) in graph[u]:
			alt = dist[u] + w_uv
			if alt < dist[v]:
				dist[v] = alt
				pred[v] = u
				if not in_queue[v]:
					if Q and dist[v] < dist[Q[-1]]:
						Q.append(v)
					else:
						Q.appendleft(v)
					in_queue[v] = True
	if dist[target] == INF:
		return '-1'
	else:
		st = []
		u = target
		while True:
			st.append(u)
			if u == pred[u]:
				break
			u = pred[u]
		st.reverse()
		path = ' '.join([str(c + 1) for c in st])
		path = path.rstrip()
		return path

def main():
	(n, m) = [int(x) for x in stdin.readline().split()]
	graph_neighbors_in_dict = [{} for _ in range(n)]
	for _ in range(m):
		(a, b, w) = [int(c) for c in stdin.readline().split()]
		w = int(w)
		a -= 1
		b -= 1
		if not b in graph_neighbors_in_dict[a]:
			graph_neighbors_in_dict[a][b] = w
		else:
			graph_neighbors_in_dict[a][b] = min(graph_neighbors_in_dict[a][b], w)
		if not a in graph_neighbors_in_dict[b]:
			graph_neighbors_in_dict[b][a] = w
		else:
			graph_neighbors_in_dict[b][a] = min(graph_neighbors_in_dict[b][a], w)
	graph = [[] for u in range(n)]
	for u in range(n):
		for (v, w) in graph_neighbors_in_dict[u].items():
			graph[u].append((v, w))
	for u in range(n):
		graph[u].sort(key=itemgetter(1))
	source = 0
	target = n - 1
	stdout.write(moore(graph, source, target))
main()


import math, sys
from collections import defaultdict, deque
from heapq import heapify, heappop, heappush
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		d = defaultdict(list)
		(n, m) = In()
		parent = [i for i in range(n + 1)]
		dist = [P] * (n + 1)
		for i in range(m):
			(a, b, c) = In()
			d[a].append((b, c))
			d[b].append((a, c))
		pq = []
		dist[1] = 0
		heappush(pq, (0, 1))
		while pq:
			node = heappop(pq)
			for x in d[node[1]]:
				(v, wieght) = (x[0], x[1])
				if dist[v] > dist[node[1]] + wieght:
					dist[v] = dist[node[1]] + wieght
					parent[v] = node[1]
					heappush(pq, (dist[v], v))
		ans = []
		node = n
		if dist[node] == P:
			print(-1)
			return
		while parent[node] != node:
			ans.append(node)
			node = parent[node]
		ans.append(node)
		print(*ans[::-1])
	except:
		pass
M = 998244353
P = 1000000000000007
for _ in range(1):
	main()


from heapq import *
(n, m) = map(int, input().split())
dis = [1000000000000000] * (n - 1) + [0]
q = [(0, n - 1)]
adj = [[] for _ in range(n)]
pre = [n] * n
for i in range(m):
	(u, v, w) = map(int, input().split())
	adj[u - 1].append((v, w))
	adj[v - 1].append((u, w))
while q:
	(w, u) = heappop(q)
	if u == 0:
		break
	for (v, cost) in adj[u]:
		if dis[v - 1] > w + cost:
			dis[v - 1] = w + cost
			pre[v - 1] = u
			heappush(q, (dis[v - 1], v - 1))
pos = 0
lst = []
while pos <= n - 1:
	lst.append(pos + 1)
	pos = pre[pos]
if lst[len(lst) - 1] == n:
	print(*[i for i in lst])
else:
	print(-1)


import heapq
import sys
input = sys.stdin.readline
INF = 1 << 60
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v, w) = map(int, input().split())
	graph[u].append((v, w))
	graph[v].append((u, w))
dist = [INF] * (n + 1)
parent = [-1] * (n + 1)
dist[1] = 0
pq = [(0, 1)]
while pq:
	(du, u) = heapq.heappop(pq)
	if du > dist[u]:
		continue
	for (v, w) in graph[u]:
		if dist[u] + w < dist[v]:
			dist[v] = dist[u] + w
			parent[v] = u
			heapq.heappush(pq, (dist[v], v))
if dist[n] == INF:
	print(-1)
else:
	cur = n
	ans = []
	while cur != -1:
		ans.append(cur)
		cur = parent[cur]
	print(*ans[::-1])


import math
from collections import defaultdict
from heapq import heappush, heappop

def solve(g, weights, n):
	tree = set()
	parent = [-1 for i in range(n + 1)]
	dist = [math.inf for i in range(n + 1)]
	v = 1
	dist[v] = 0
	q = [(0, v)]
	tree.add(v)
	while len(q):
		(_, v) = heappop(q)
		tree.add(v)
		if v == n:
			break
		for neigh in g[v]:
			w = weights[min(v, neigh), max(v, neigh)]
			if dist[v] + w < dist[neigh]:
				dist[neigh] = dist[v] + w
				parent[neigh] = v
				heappush(q, (dist[v] + w, neigh))
	if parent[n] == -1:
		print(-1)
		return
	path = []
	v = n
	while v != -1:
		path.append(v)
		v = parent[v]
	path.reverse()
	for p in path:
		print(p, end=' ')
	print()

def build_graph(n, m):
	g = defaultdict(list)
	weights = defaultdict(lambda : math.inf)
	for i in range(m):
		(u, v, w) = list(map(int, input().split(' ')))
		g[u].append(v)
		g[v].append(u)
		(u_, v_) = (min(u, v), max(u, v))
		weights[u_, v_] = min(weights[u_, v_], w)
	return (g, weights)
(n, m) = list(map(int, input().split(' ')))
(g, w) = build_graph(n, m)
solve(g, w, n)


from heapq import *
INT_MAX = 1 << 60

def main():
	(n, m) = map(int, input().split())
	g = [[] for _ in range(n)]
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		g[a - 1].append([c, b - 1])
		g[b - 1].append([c, a - 1])
	dis = [INT_MAX] * n
	vis = [0] * n
	parent = [-1] * n
	que = [[0, 0]]
	dis[0] = 0
	while que:
		u = heappop(que)[1]
		if vis[u]:
			continue
		vis[u] = 1
		for item in g[u]:
			(w, v) = item
			if vis[v]:
				continue
			if dis[u] + w < dis[v]:
				dis[v] = dis[u] + w
				parent[v] = u
				heappush(que, [dis[v], v])
	if dis[n - 1] == INT_MAX:
		print('-1')
		return
	i = n - 1
	path = []
	while i != -1:
		path.append(str(i + 1))
		i = parent[i]
	print(' '.join(path[::-1]))
main()


from collections import defaultdict as df
import heapq
from sys import stdin, stdout
h = []
heapq.heapify(h)
d = df(list)
(n, m) = list(map(int, stdin.readline().split()))
for i in range(m):
	(a, b, c) = list(map(int, stdin.readline().split()))
	d[a].append((b, c))
	d[b].append((a, c))
visited = [0] * (n + 1)
heapq.heappush(h, [0, 1])
dist = [float('inf')] * (n + 1)
dist[1] = 0
ans = []
p = [-1] * (n + 1)
ans.append(1)
while len(h) > 0:
	(k, temp) = heapq.heappop(h)
	visited[temp] = True
	for (j, dis) in d[temp]:
		if visited[j] == False or dist[j] > k + dis or dist[j] == float('inf'):
			r = k + dis
			if r < dist[j]:
				dist[j] = r
				p[j] = temp
				heapq.heappush(h, [dist[j], j])
if dist[n] == float('inf'):
	stdout.write(str(-1))
else:
	(x, y) = (n, [])
	while x != -1:
		y += [x]
		x = p[x]
	y.reverse()
	stdout.write(' '.join(map(str, y)))


import heapq
import sys
stdin = sys.stdin.read().split()
(n, m, *edges) = map(int, stdin)
V = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b, w) = (edges[i * 3], edges[i * 3 + 1], edges[i * 3 + 2])
	V[a].append((b, w))
	V[b].append((a, w))
visited = [False] * (n + 1)
prev = [None] * (n + 1)
node = 1
dist = [float('inf')] * (n + 1)
dist[node] = 0
Q = [(dist[node], node) for node in range(n + 1)]
heapq.heapify(Q)
while Q:
	(_, node) = heapq.heappop(Q)
	if visited[node]:
		continue
	for (dst_node, weight) in V[node]:
		if dist[node] + weight < dist[dst_node]:
			dist[dst_node] = dist[node] + weight
			prev[dst_node] = node
			heapq.heappush(Q, (dist[dst_node], dst_node))
	visited[node] = True
if prev[n]:
	output = []
	node = n
	while node != 1:
		output.append(node)
		node = prev[node]
	output.append(1)
	print(' '.join(map(str, reversed(output))))
else:
	print(-1)


import sys
sys.setrecursionlimit(10 ** 6)
debug_mode = True if len(sys.argv) > 1 and sys.argv[1] == '-d' else False
if debug_mode:
	import os
	inf = open(os.path.abspath(__file__).replace('.py', '.in'))

	def input():
		return inf.readline()
from heapq import heappush, heappop
INF = 1 << 60

def dijkstra(G, s):
	D = {i: INF for i in range(1, len(G) + 1)}
	D[s] = 0
	(P, Q, S) = ({}, [(0, s)], set())
	while Q:
		(_, u) = heappop(Q)
		if u in S:
			continue
		S.add(u)
		for v in G[u]:
			d = D[u] + G[u][v]
			if d < D[v]:
				(D[v], P[v]) = (d, u)
			heappush(Q, (D[v], v))
	return (D, P)

def main():
	(n, m) = list(map(int, input().strip().split()))
	G = {i: {} for i in range(1, n + 1)}
	for _ in range(m):
		(a, b, w) = list(map(int, input().strip().split()))
		(G[a][b], G[b][a]) = (w, w)
	(D, P) = dijkstra(G, 1)
	if D[n] == INF:
		print(-1)
		return
	path = [n]
	u = n
	while u != 1:
		path.append(P[u])
		u = P[u]
	print(' '.join((str(i) for i in path[::-1])))
main()
if debug_mode:
	inf.close()


from heapq import heappush, heappop
from sys import maxsize
(vertexes, edges) = map(int, input().split())
graph = [[] for i in range(vertexes + 1)]
for _ in range(edges):
	(from_, to_, cost_) = map(int, input().split())
	graph[from_].append([to_, cost_])
	graph[to_].append([from_, cost_])

def Dijekstra(node: int):
	visited = (vertexes + 1) * [False]
	parent = (vertexes + 1) * [-1]
	distance = [0] + vertexes * [float('inf')]
	heap = []
	heappush(heap, (0, node, -1))
	while heap:
		(cost, current_node, parent_) = heappop(heap)
		if visited[current_node]:
			continue
		visited[current_node] = True
		parent[current_node] = parent_
		for (child_node, child_cost) in graph[current_node]:
			if not visited[child_node] and cost + child_cost < distance[child_node]:
				heappush(heap, (child_cost + cost, child_node, current_node))
	path = []
	node_ = vertexes
	while node_ != -1:
		path.append(node_)
		node_ = parent[node_]
	print(' '.join(map(str, reversed(path))) if len(path) > 1 else -1)
Dijekstra(1)


import heapq
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

def dijkstra(adj, source, target):
	INF = ((1 << 63) - 1) // 2
	pred = {x: x for x in adj}
	dist = {x: INF for x in adj}
	dist[source] = 0
	PQ = []
	heapq.heappush(PQ, [dist[source], source])
	while PQ:
		u = heapq.heappop(PQ)
		u_dist = u[0]
		u_id = u[1]
		if u_dist == dist[u_id]:
			for v in adj[u_id]:
				v_id = v[0]
				w_uv = v[1]
				if dist[u_id] + w_uv < dist[v_id]:
					dist[v_id] = dist[u_id] + w_uv
					heapq.heappush(PQ, [dist[v_id], v_id])
					pred[v_id] = u_id
	if target not in dist or dist[target] == INF:
		raise Exception('Invalid path')
	else:
		st = []
		node = target
		while True:
			st.append(str(node))
			if node == pred[node]:
				break
			node = pred[node]
		return st[::-1]
(n, m) = map(int, input().split())
graph = dict()
for i in range(m):
	(a, b, w) = map(int, input().split())
	if a in graph:
		graph[a].append((b, w))
	else:
		graph[a] = [(b, w)]
	if b in graph:
		graph[b].append((a, w))
	else:
		graph[b] = [(a, w)]
try:
	print(*map(int, dijkstra(graph, 1, n)))
except:
	print(-1)


from heapq import heappop, heappush
from sys import stdin

def make_graph(m):
	graph_dict = {}
	for i in range(m):
		s = input()
		(u, v, w) = (int(t) for t in s.split())
		if u not in graph_dict:
			graph_dict[u] = {}
		if v not in graph_dict:
			graph_dict[v] = {}
		graph_dict[u][v] = w
		graph_dict[v][u] = w
	return graph_dict

class node_type:

	def __init__(self, vertex, distance):
		self.vertex = vertex
		self.distance = distance

	def __lt__(self, rhs):
		return self.distance < rhs.distance

def find_path(graph_dict, begin_vertex, end_vertex):
	node = node_type(end_vertex, 0)
	node_dict = {end_vertex: node}
	queue = []
	heappush(queue, node)
	while queue:
		from_node = heappop(queue)
		if from_node.vertex == begin_vertex:
			return node_dict
		if from_node.vertex in graph_dict:
			for to_vertex in graph_dict[from_node.vertex]:
				distance = from_node.distance + graph_dict[from_node.vertex][to_vertex]
				if to_vertex not in node_dict or distance < node_dict[to_vertex].distance:
					node_dict[to_vertex] = node_type(from_node.vertex, distance)
					heappush(queue, node_type(to_vertex, distance))
	return None

def test_case(n, m):
	begin_vertex = 1
	end_vertex = n
	graph_dict = make_graph(m)
	node_dict = find_path(graph_dict, begin_vertex, end_vertex)
	if not node_dict:
		print('-1')
		return
	path_list = [begin_vertex]
	while begin_vertex != end_vertex:
		begin_vertex = node_dict[begin_vertex].vertex
		path_list.append(begin_vertex)
	print(' '.join((str(v) for v in path_list)))

def main():
	for s in stdin:
		(n, m) = (int(t) for t in s.split())
		test_case(n, m)
main()


from sys import stdin, stdout
input = stdin.readline
from collections import defaultdict as dd
from heapq import heappop, heappush
import math

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def gets():
	return input()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	(n, m) = geti()
	target = n - 1
	edges = dd(list)
	weight = []
	seen = set()
	mini = [float('inf')] * n
	parent = [None] * n
	for i in range(m):
		(u, v, w) = geti()
		u -= 1
		v -= 1
		edges[u].append((v, w))
		edges[v].append((u, w))
	heappush(weight, [0, 0, None])
	while weight:
		(cost, node, par) = heappop(weight)
		if node in seen:
			continue
		seen.add(node)
		mini[node] = cost
		parent[node] = par
		if node == target:
			break
		for (child, price) in edges[node]:
			if child in seen:
				continue
			if mini[child] > mini[node] + price:
				mini[child] = mini[node] + price
				heappush(weight, [mini[child], child, node])
	path = []
	node = target
	while node != None:
		path.append(node + 1)
		node = parent[node]
	path.reverse()
	if 1 not in path:
		print(-1)
	else:
		print(*path)
solve()


import heapq
from collections import defaultdict

def solve(n):
	distances = [10 ** 18 for i in range(n + 5)]
	Q = list()
	heapq.heappush(Q, (0, 1))
	paths[1] = 1
	distances[1] = 0
	while Q:
		(c, u) = heapq.heappop(Q)
		if u == n:
			return c
		if distances[u] < c:
			continue
		for (w, v) in Graph[u]:
			if distances[v] > c + w:
				distances[v] = c + w
				heapq.heappush(Q, (distances[v], v))
				paths[v] = u
	return -1
Graph = defaultdict(list)
paths = defaultdict(int)
arr = list()
(n, m) = map(int, input().split())
for i in range(m):
	(x, y, c) = map(int, input().split())
	Graph[x].append((c, y))
	Graph[y].append((c, x))
if solve(n) != -1:
	while paths[n] != n:
		arr.append(n)
		n = paths[n]
else:
	print(-1)
	exit()
arr.append(1)
print(' '.join(map(str, arr[::-1])))


from heapq import *
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
dat = [[] for i in range(n + 1)]
for i in range(1, m + 1):
	(a, b, w) = map(int, input().split())
	dat[a].append([b, w])
	dat[b].append([a, w])
dis = [float('inf') for i in range(n + 1)]
path = [0 for i in range(n + 1)]
q = [(0, 1)]
while q:
	(s1, s2) = heappop(q)
	for (b, w) in dat[s2]:
		if dis[b] > s1 + w:
			path[b] = s2
			dis[b] = s1 + w
			heappush(q, (dis[b], b))
if path[n] == 0:
	print('-1')
else:
	ret = [n]
	i = n
	while i > 1:
		i = path[i]
		ret.append(i)
	print(*ret[::-1])


import heapq
import math

class DuplicatePriorityQueue:

	def __init__(self):
		self.heap = []

	def push(self, key, value):
		heapq.heappush(self.heap, (key, value))

	def pop(self):
		return heapq.heappop(self.heap)

	def empty(self):
		return len(self.heap) == 0

class Graph:

	def __init__(self, v=0):
		self.adjacency_list = [[] for _ in range(v)]

	def add_vertex(self):
		self.adjacency_list.append([])

	def add_undirected_edge(self, u, v, weight=1):
		self.adjacency_list[u].append((v, weight))
		self.adjacency_list[v].append((u, weight))

	def __getitem__(self, i):
		return self.adjacency_list[i]

	def __iter__(self):
		yield from self.adjacency_list

	def __len__(self):
		return len(self.adjacency_list)

def dijkstra(graph, source):
	distances = [math.inf for node in graph]
	distances[source] = 0
	pred = [None] * len(graph)
	priority_queue = DuplicatePriorityQueue()
	priority_queue.push(0, source)
	while not priority_queue.empty():
		(distance, v) = priority_queue.pop()
		if distance > distances[v]:
			continue
		for (u, w) in graph[v]:
			if distance + w < distances[u]:
				distances[u] = distance + w
				pred[u] = v
				priority_queue.push(distance + w, u)
	return (distances, pred)

def path(v, pred, labels, source=None):
	indexes = []
	current = v
	while current is not None:
		indexes.append(current)
		current = pred[current]
	if source is not None and indexes[-1] != source:
		raise ValueError('No path exists')
	return ' '.join(reversed(list((labels[i] for i in indexes))))
(n, m) = map(int, input().split())
graph = Graph(n)
for _ in range(m):
	(u, v, w) = map(int, input().split())
	graph.add_undirected_edge(u - 1, v - 1, w)
(distances, pred) = dijkstra(graph, 0)
labels = list(map(str, range(1, n + 1)))
try:
	print(path(n - 1, pred, labels, 0))
except ValueError:
	print('-1')


import heapq
(n, m) = map(int, input().split())
g = {i: [] for i in range(1, n + 1)}
dis = [float('inf') for i in range(n + 1)]
visited = [False for i in range(n + 1)]
for i in range(m):
	(a, b, w) = map(int, input().split())
	g[a].append((b, w))
	g[b].append((a, w))
q = []
p = [-1 for i in range(n + 1)]
dis[1] = 0
heapq.heappush(q, [0, 1])
while q:
	a = heapq.heappop(q)
	(curdis, curnode) = a
	if visited[curnode] == True:
		continue
	visited[curnode] = True
	for (child, distance) in g[curnode]:
		if visited[child] == False and distance + curdis < dis[child]:
			dis[child] = distance + curdis
			p[child] = curnode
			heapq.heappush(q, [dis[child], child])
if dis[n] == float('inf'):
	print(-1)
else:
	path = []
	while n > 0:
		path.append(n)
		n = p[n]
	path.reverse()
	print(*path)


import sys
from heapq import *
inf = int(1000000000000.0)
(n, m) = map(int, input().split())
parent = [-1] * n
dis = [inf] * n
graph = [[] for i in range(n)]
dis[0] = 0
for i in range(m):
	(a, b, c) = map(int, input().split())
	graph[a - 1].append((b - 1, c))
	graph[b - 1].append((a - 1, c))
q = [(0, 0)]
while q:
	(w, node) = heappop(q)
	for nodes in graph[node]:
		if dis[nodes[0]] > dis[node] + nodes[1]:
			dis[nodes[0]] = dis[node] + nodes[1]
			parent[nodes[0]] = node
			heappush(q, (dis[nodes[0]], nodes[0]))
if parent[n - 1] == -1:
	print(-1)
else:
	path = []
	s = n - 1
	while s != -1:
		path.append(s + 1)
		s = parent[s]
	path.reverse()
	print(*path)


import sys
from random import choice, randint
inp = sys.stdin.readline
out = sys.stdout.write
flsh = sys.stdout.flush
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def MI():
	return map(int, inp().strip().split())

def LI():
	return list(map(int, inp().strip().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]

def LI_():
	return [int(x) - 1 for x in inp().strip().split()]

def LF():
	return [float(x) for x in inp().strip().split()]

def LS():
	return inp().strip().split()

def I():
	return int(inp().strip())

def F():
	return float(inp().strip())

def S():
	return inp().strip()

def pf(s):
	return out(s + '\n')

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))
from collections import defaultdict, deque
from heapq import heapify, heappop, heappush

class Graph:

	def __init__(self, V):
		self.v = V
		self.graph = defaultdict(list)

	def addedge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def addedge_weight(self, u, v, w):
		self.graph[u].append((w, v))
		self.graph[v].append((w, u))

	def bfs(self, s):
		visited = [False] * self.v
		q = deque()
		q.append(s)
		visited[s] = True
		parent = [-1] * self.v
		depth = [-1] * self.v
		depth[s] = 0
		while len(q) > 0:
			x = q.popleft()
			for u in self.graph[x]:
				if not visited[u]:
					q.append(u)
					visited[u] = True
					depth[u] = depth[x] + 1
					parent[u] = x

	def dfsutil(self, visited, s):
		visited[s] = True
		for u in self.graph[s]:
			if not visited[u]:
				self.dfsutil(visited, u)

	def dfs(self, s):
		visited = [False] * self.v
		self.dfsutil(self, visited, s)

	def dijkstras(self, s):
		dist = [inf] * self.v
		parent = [-1] * self.v
		q = []
		heappush(q, (0, s))
		dist[s] = 0
		while q:
			(w, u) = heappop(q)
			for i in self.graph[u]:
				(wg, v) = i
				if dist[v] > dist[u] + wg:
					dist[v] = dist[u] + wg
					parent[v] = u
					heappush(q, (dist[v], v))
		if dist[self.v - 1] == inf:
			return [-1]
		else:
			(x, y) = (self.v - 1, [])
			while x != -1:
				y.append(x + 1)
				x = parent[x]
			y.reverse()
			return y

def main():
	(n, m) = MI()
	g = Graph(n)
	for _ in range(m):
		(a, b, w) = MI()
		a -= 1
		b -= 1
		g.addedge_weight(a, b, w)
	x = g.dijkstras(0)
	pf(JA(x, ' '))
main()


import heapq as hp
import sys
G = {}
V = {}
D = {}
pq = []
inf = 10000000000000000000
Par = {}
(N, M) = map(int, input().split())
for i in range(1, N + 1):
	G[i] = []
	V[i] = 0
	D[i] = inf
	Par[i] = -1
for m in range(M):
	(a, b, w) = map(int, input().split())
	G[a].append([w, b])
	G[b].append([w, a])
hp.heappush(pq, (0, 1))
while pq:
	D[1] = 0
	curr = hp.heappop(pq)
	v = curr[1]
	w = curr[0]
	for x in G[v]:
		if w + x[0] < D[x[1]]:
			D[x[1]] = w + x[0]
			Par[x[1]] = v
			hp.heappush(pq, (D[x[1]], x[1]))
if D[N] == inf:
	print(-1)
else:
	p = N
	a = []
	while p != -1:
		a.append(p)
		p = Par[p]
	for i in a[::-1]:
		print(i, end=' ')
	print()


from heapq import heappush as push, heappop as pop
from collections import defaultdict
(N, M) = map(int, input().split())
adj = defaultdict(lambda : defaultdict(lambda : []))
for _ in range(M):
	(u, v, w) = map(int, input().split())
	adj[u - 1][v - 1].append(w)
	adj[v - 1][u - 1].append(w)
pq = []
dist = [10 ** 8] * N
visited = set()
backptr = [-1] * N
push(pq, (0, 0, -1))
while pq:
	(d, u, p) = pop(pq)
	if u in visited:
		continue
	visited.add(u)
	dist[u] = d
	backptr[u] = p
	for v in adj[u]:
		for d2 in adj[u][v]:
			push(pq, (d + d2, v, u))
if backptr[N - 1] == -1:
	print(-1)
else:
	node = N - 1
	path = []
	while node != -1:
		path.append(str(node + 1))
		node = backptr[node]
	print(' '.join(path[::-1]))


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
G = defaultdict(list)
inf = float('inf')

def addEdge(a, b, w):
	G[a].append([b, w])
	G[b].append([a, w])

def difun(N, source):
	dist = [inf] * (N + 1)
	path = [i for i in range(N + 1)]
	pq = [[0, source]]
	heapq.heapify(pq)
	dist[source] = 0
	while pq:
		(curr_d, curr) = heapq.heappop(pq)
		for (i, j) in G[curr]:
			if curr_d + j < dist[i]:
				dist[i] = curr_d + j
				path[i] = curr
				heapq.heappush(pq, [dist[i], i])
	return (dist, path)
(N, M) = ilele()
for i in range(M):
	(a, b, c) = ilele()
	addEdge(a, b, c)
source = 1
desti = N
(dist, path) = difun(N, source)
if dist[N] == float('inf'):
	print(-1)
else:
	p = [desti]
	x = desti
	while x != source:
		x = path[x]
		p.append(x)
	print(*p[::-1])


from collections import defaultdict
from heapq import heappush, heappop

def main():
	(n, m) = input_tuple(int)
	adj_list = defaultdict(lambda : [])
	for _ in range(m):
		(u, v, w) = input_tuple(int)
		adj_list[u].append((v, w))
		adj_list[v].append((u, w))
	pred = {1: -1}
	dist = defaultdict(lambda : float('inf'))
	dist[1] = 0
	heap = [(0, 1)]
	seen = set()
	while heap:
		(_, u) = heappop(heap)
		seen.add(u)
		for (v, w) in adj_list[u]:
			if v in seen:
				continue
			new_dist = dist[u] + w
			if dist[v] > new_dist:
				dist[v] = new_dist
				pred[v] = u
				heappush(heap, (dist[v], v))
	if n in pred:
		i = n
		path = []
		while i > 0:
			path.append(str(i))
			i = pred[i]
		print(' '.join(path[::-1]))
	else:
		print(-1)

def input_tuple(f):
	return tuple(map(f, input().rstrip().split()))
main()


import sys, os.path
from collections import *
from heapq import *
from copy import *
import math
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
g = defaultdict(list)
for i in range(m):
	(a, b, w) = map(int, input().split())
	g[a].append((b, w))
	g[b].append((a, w))
vis = set()
dis = [10000000000000000 for i in range(n + 1)]
dis[0] = 0
dis[1] = 0
hp = [(0, 1)]
parent = [-1 for i in range(n + 1)]
while len(hp) > 0:
	(distu, u) = heappop(hp)
	for i in g[u]:
		v = i[0]
		wt = i[1]
		if dis[v] > dis[u] + wt:
			parent[v] = u
			dis[v] = dis[u] + wt
			heappush(hp, (dis[v], v))
path = []
last = n
if parent[n] == -1:
	print('-1')
else:
	while last != -1:
		path.append(last)
		last = parent[last]
	path.reverse()
	print(*path)


import heapq

def dijkstra(adj, source, target):
	INF = ((1 << 63) - 1) // 2
	pred = {x: x for x in adj}
	dist = {x: INF for x in adj}
	pred_b = {x: x for x in adj}
	dist_b = {x: INF for x in adj}
	dist[source] = 0
	dist_b[target] = 0
	Q = []
	Q_b = []
	S = set()
	S_b = set()
	heapq.heappush(Q, [dist[source], source])
	heapq.heappush(Q_b, [dist_b[target], target])
	found_common_node = False
	while Q and Q_b:
		u = heapq.heappop(Q_b)
		u_dist = u[0]
		u_id = u[1]
		S_b.add(u_id)
		if u_dist == dist_b[u_id]:
			if u_id in S:
				found_common_node = True
				break
			for v in adj[u_id]:
				v_id = v[0]
				w_uv = v[1]
				if dist_b[u_id] + w_uv < dist_b[v_id]:
					dist_b[v_id] = dist_b[u_id] + w_uv
					heapq.heappush(Q_b, [dist_b[v_id], v_id])
					pred_b[v_id] = u_id
		u = heapq.heappop(Q)
		u_dist = u[0]
		u_id = u[1]
		S.add(u_id)
		if u_dist == dist[u_id]:
			if u_id == target:
				break
			if u_id in S_b:
				found_common_node = True
				break
			for v in adj[u_id]:
				v_id = v[0]
				w_uv = v[1]
				if dist[u_id] + w_uv < dist[v_id]:
					dist[v_id] = dist[u_id] + w_uv
					heapq.heappush(Q, [dist[v_id], v_id])
					pred[v_id] = u_id
	if not Q_b and (not found_common_node):
		if dist_b[source] == INF:
			print('-1')
			return
		else:
			st = []
			node = source
			while True:
				st.append(str(node))
				if node == pred_b[node]:
					break
				node = pred_b[node]
			path = st
			print(' '.join(path))
			return
	if not Q and (not found_common_node):
		if dist[target] == INF:
			print('-1')
			return
		else:
			st = []
			node = target
			while True:
				st.append(str(node))
				if node == pred[node]:
					break
				node = pred[node]
			path = st[::-1]
			print(' '.join(path))
			return
	if not found_common_node:
		print(-1)
	else:
		nodes_in_Q = set()
		while Q:
			u = heapq.heappop(Q)
			u_id = u[1]
			nodes_in_Q.add(u_id)
		nodes_in_Q_b = set()
		while Q_b:
			u = heapq.heappop(Q_b)
			u_id = u[1]
			nodes_in_Q_b.add(u_id)
		candidates = (S | nodes_in_Q) & (S_b | nodes_in_Q_b)
		min_dist = INF
		min_node = 'none'
		for node in candidates:
			middle_dist = dist[node] + dist_b[node]
			if middle_dist < min_dist:
				min_dist = middle_dist
				min_node = node
		st = []
		node = min_node
		while True:
			st.append(str(node))
			if node == pred[node]:
				break
			node = pred[node]
		path_forward = st[::-1]
		st = []
		node = min_node
		while True:
			st.append(str(node))
			if node == pred_b[node]:
				break
			node = pred_b[node]
		path = ' '.join(path_forward) + ' ' + ' '.join(st[1:])
		print(path)

def main():
	(n, m) = [int(c) for c in input().split()]
	adj = {i: [] for i in range(1, n + 1)}
	for i in range(m):
		(a, b, w) = [int(c) for c in input().split()]
		adj[a].append((b, w))
		adj[b].append((a, w))
	source = 1
	target = n
	dijkstra(adj, source, target)
main()


import heapq
(k, m) = map(int, input().split())
adj = {}
for i in range(1, k + 1):
	adj[i] = []
for i in range(m):
	(u, v, w) = map(int, input().split())
	adj[u].append([v, w])
	adj[v].append([u, w])
d = {}
for i in range(1, k + 1):
	d[i] = float('inf')
d[1] = 0
q = []
p = {}
heapq.heappush(q, (0, 1))
while q:
	(last_w, curr_v) = heapq.heappop(q)
	for (n, n_w) in adj[curr_v]:
		cand_w = last_w + n_w
		if cand_w < d[n]:
			d[n] = cand_w
			p[n] = curr_v
			heapq.heappush(q, (cand_w, n))
if d[k] != float('inf'):
	l = [k]
	x = k
	while x != 1:
		x = p[x]
		l.append(x)
	l.reverse()
	print(*l)
else:
	print(-1)


from collections import defaultdict
from heapq import *
__author__ = 'artyom'

def dijkstra(edges, f, t):
	g = defaultdict(list)
	for (l, r, c) in edges:
		g[l].append((c, r))
	(q, seen) = ([(0, f, ())], set())
	while q:
		(cost, v1, path) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			path = (v1, path)
			if v1 == t:
				return path
			for (c, v2) in g.get(v1, ()):
				if v2 not in seen:
					heappush(q, (cost + c, v2, path))
	return -1
read = lambda : map(int, input().split())
(n, m) = read()
edges = []
for _ in range(m):
	edge = list(read())
	edges.append(edge)
	edges.append((edge[1], edge[0], edge[2]))
ans = dijkstra(edges, 1, n)
if ans != -1:
	path = []
	while ans:
		path.append(ans[0])
		ans = ans[1]
	print(' '.join(map(str, reversed(path))))
else:
	print(ans)


from heapq import heappop, heappush
infinite = 1 << 60
(vertices, edges) = map(int, input().split())
graph = [[] for _ in range(vertices)]
distance = [0] + [infinite] * (vertices - 1)
path = [-1] * vertices
queue = [(0, 0)]
i = 0
while i < edges:
	(a, b, w) = map(int, input().split())
	graph[a - 1].append((w, b - 1))
	graph[b - 1].append((w, a - 1))
	i += 1
while queue:
	(d, u) = heappop(queue)
	if d >= distance[u]:
		for element in graph[u]:
			(d_new, v) = (element[0] + distance[u], element[1])
			if d_new < distance[v]:
				(distance[v], path[v]) = (d_new, u)
				heappush(queue, (distance[v], v))
if distance[vertices - 1] == infinite:
	print(-1)
else:
	(x, a) = (vertices - 1, [])
	while x != -1:
		a += [x + 1]
		x = path[x]
	a.reverse()
	print(' '.join(map(str, a)))


from heapq import heappush, heappop
(n, m) = map(int, input().split(' '))
g = [[] for i in range(n)]
for i in range(m):
	(a, b, w) = map(int, input().split(' '))
	a -= 1
	b -= 1
	g[a].append((b, w))
	g[b].append((a, w))
h = [(0, 0)]
d = [2 ** 40 for i in range(n)]
parents = [None for i in range(n)]
while h:
	(di, v) = heappop(h)
	for (u, w) in g[v]:
		if d[u] > di + w:
			parents[u] = v
			d[u] = di + w
			heappush(h, (d[u], u))
if parents[n - 1] == None:
	print(-1)
	exit(0)
(res, v) = ([n], n - 1)
while v != 0:
	v = parents[v]
	res.append(v + 1)
print(*res[::-1])


import sys
from heapq import heappop, heappush
input = sys.stdin.readline
inf = 10 ** 16 + 7
(n, m) = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(m):
	(u, v, w) = map(int, input().split())
	adj[u - 1].append((w, v - 1))
	adj[v - 1].append((w, u - 1))
d = [inf] * n
trace = [-1] * n
d[0] = 0
q = [(d[0], 0)]
while q:
	(du, u) = heappop(q)
	if du == d[u]:
		for (w, v) in adj[u]:
			if d[v] > d[u] + w:
				(d[v], trace[v]) = (d[u] + w, u)
				heappush(q, (d[v], v))
u = n - 1
if d[u] == inf:
	print(-1)
else:
	st = []
	while u != -1:
		st.append(u + 1)
		u = trace[u]
	print(*reversed(st))


import os
import sys
from bisect import bisect_right
from collections import Counter, defaultdict
from heapq import *
from io import BytesIO, IOBase
from math import gcd, inf, sqrt, ceil

def lcm(a, b):
	return a * b // gcd(a, b)

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def printDivisors(n):
	i = 2
	z = [1, n]
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def cheaker(a):
	j = 1
	p = False
	for i in a:
		if i != j:
			break
		j += 1
	q = len(a)
	for i in a[::-1]:
		if i != q:
			break
		q -= 1
	for i in range(j - 1, q):
		if a[i] == i + 1:
			return False
	return True

def create(n, x, f):
	pq = len(bin(n)[2:])
	if f == 0:
		tt = min
	else:
		tt = max
	dp = [[inf] * n for _ in range(pq)]
	dp[0] = x
	for i in range(1, pq):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = tt(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def enquiry(l, r, dp, f):
	if l > r:
		return inf if not f else -inf
	if f == 1:
		tt = max
	else:
		tt = min
	pq1 = len(bin(r - l + 1)[2:]) - 1
	return tt(dp[pq1][l], dp[pq1][r - (1 << pq1) + 1])

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x

def main():
	from math import inf

	class dijkstra:

		def __init__(self, n):
			self.n = n
			self.adj = [[] for j in range(self.n + 1)]
			self.d = [10 ** 20] * (self.n + 1)
			self.p = [-1] * (self.n + 1)
			self.vis = [0] * (self.n + 1)

		def dijs(self, s):
			self.d[s] = 0
			heap = [[0, s]]
			heapify(heap)
			while heap:
				v = heappop(heap)[1]
				if self.vis[v]:
					continue
				self.vis[v] = 1
				for edge in self.adj[v]:
					(i, j) = edge
					if not self.vis[i] and self.d[i] > self.d[v] + j:
						self.d[i] = self.d[v] + j
						heappush(heap, (self.d[i], i))
						self.p[i] = v

		def path(self, s, t):
			pa = []
			i = t
			while i != s and i != -1:
				pa.append(i)
				i = self.p[i]
			if i == -1:
				return [1]
			pa.append(s)
			return pa[::-1]
	(n, m) = map(int, input().split())
	x = dijkstra(n)
	for i in range(m):
		(a, b, w) = map(int, input().split())
		x.adj[a].append([b, w])
		x.adj[b].append([a, w])
	x.dijs(1)
	xx = x.path(1, n)
	if xx[-1] == 1:
		print(-1)
	else:
		print(*xx)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
import heapq

def main():
	(n, m) = map(int, input().split())
	adj = [[] for i in range(n)]
	for i in range(m):
		(a, b, w) = map(int, input().split())
		adj[a - 1].append((b - 1, w))
		adj[b - 1].append((a - 1, w))

	def djikstra(x, end):
		n = len(adj)
		visited = [False] * n
		path = []
		distances = [math.inf] * n
		distances[x] = 0
		pre = [-1] * n
		pq = list()
		heapq.heapify(pq)
		heapq.heappush(pq, (0, x))
		while pq:
			(distance, node) = heapq.heappop(pq)
			for next in adj[node]:
				el = next[0]
				w = next[1]
				if distances[node] + w < distances[el]:
					pre[el] = node
					distances[el] = distances[node] + w
					heapq.heappush(pq, (distances[el], el))
		if pre[end] == -1:
			print('-1')
		else:
			v = end
			while v != -1:
				path.append(pre[v])
				v = pre[v]
			path.reverse()
			path.append(end)
			path = [str(el + 1) for el in path if el != -1]
			print(' '.join(path))
	djikstra(0, n - 1)
main()


import heapq
import math

class Node:

	def __init__(self):
		self.visited = False
		self.adj = []
		self.prev = -1
		self.dist = math.inf
(N, M) = map(int, input().split())
nodes = [Node() for i in range(N + 1)]
for i in range(M):
	(u, v, w) = map(int, input().split())
	nodes[u].adj.append((v, w))
	nodes[v].adj.append((u, w))

def path(end: int) -> []:
	node = nodes[end]
	p = [end]
	while node.prev != -1:
		p.append(node.prev)
		node = nodes[node.prev]
	p.reverse()
	return p

def dijkstra(start: int, end: int) -> []:
	to_visit = [(0, start)]
	nodes[start].dist = 0
	heapq.heapify(to_visit)
	while len(to_visit) > 0:
		(dist, n) = heapq.heappop(to_visit)
		node = nodes[n]
		if node.visited:
			continue
		node.visited = True
		if n == end:
			return path(end)
		for (v, d) in node.adj:
			if nodes[v].dist > dist + d:
				nodes[v].dist = dist + d
				nodes[v].prev = n
				heapq.heappush(to_visit, (dist + d, v))
	return [-1]
p = dijkstra(1, N)
print(*p)


INF = float('inf')
import heapq as hq
from collections import defaultdict as dd

def dijkstra(g, source):
	heap = []
	heaplen = 0
	hq.heapify(heap)
	dist_to = [INF] * (n + 1)
	dist_to[source] = 0
	hq.heappush(heap, (dist_to[source], source))
	heaplen = 1
	prev = [source] * (n + 1)
	prev[source] = -1
	while heaplen > 0:
		temp = hq.heappop(heap)
		heaplen -= 1
		for edge in g[temp[1]]:
			if dist_to[temp[1]] + edge[0] < dist_to[edge[1]]:
				dist_to[edge[1]] = dist_to[temp[1]] + edge[0]
				hq.heappush(heap, (edge[0], edge[1]))
				heaplen += 1
				prev[edge[1]] = temp[1]
	return (dist_to, prev)
(n, m) = map(int, input().strip().split(' '))
g = dd(list)
for _ in range(m):
	(u, v, w) = [int(i) for i in input().split()]
	g[u].append((w, v))
	g[v].append((w, u))
source = 1
destination = n
(dist, prev) = dijkstra(g, source)
if dist[destination] == INF:
	print(-1)
else:
	p = prev[destination]
	path = [destination]
	while p != -1:
		path.append(p)
		p = prev[p]
	print(*path[::-1])


from heapq import heappop, heappush
POS_INF = float('inf')

def dijkstra(graph, source):
	q = [(0, source)]
	distto = [POS_INF] * graph.V
	distto[source] = 0
	edgeto = [None] * graph.V
	edgeto[source] = source
	marked = [False] * graph.V
	while q:
		(vweight, v) = heappop(q)
		if marked[v]:
			continue
		marked[v] = True
		for w in graph.adj(v):
			d = distto[v] + graph.weight(w, v)
			if distto[w] > d:
				distto[w] = d
				edgeto[w] = v
				heappush(q, (d, w))
	return edgeto

class Graph:

	def __init__(self, V):
		self.V = V
		self._adj = [None] * V
		self._weight = {}

	def add(self, v, w, weight):
		if not self._adj[v]:
			self._adj[v] = []
		if not self._adj[w]:
			self._adj[w] = []
		self._adj[v] += [w]
		self._adj[w] += [v]
		(v, w) = (v, w) if v < w else (w, v)
		self._weight[v, w] = weight

	def adj(self, v):
		return self._adj[v] or []

	def weight(self, v, w):
		(v, w) = (v, w) if v < w else (w, v)
		return self._weight.get((v, w), POS_INF)

def test1():
	g = Graph(1)
	tree = dijkstra(g, 0)
	assert tree == [0], tree
	print('test 1 - YEAH')

def test2():
	g = Graph(2)
	g.add(0, 1, 1)
	tree = dijkstra(g, 0)
	assert tree == [0, 0], tree
	print('test 2 - YEAH')

def test3():
	g = Graph(3)
	g.add(0, 1, 1)
	g.add(0, 2, 2)
	tree = dijkstra(g, 0)
	assert tree == [0, 0, 0], tree
	print('test 3 - YEAH')

def test4():
	g = Graph(10)
	g.add(0, 1, 1)
	g.add(1, 2, 1)
	g.add(2, 3, 1)
	g.add(3, 4, 1)
	g.add(4, 5, 1)
	g.add(0, 6, 2)
	g.add(6, 7, 2)
	g.add(7, 8, 2)
	g.add(8, 9, 2)
	tree = dijkstra(g, 0)
	assert tree == [0, 0, 1, 2, 3, 4, 0, 6, 7, 8], tree
	print('test 4 - YEAH')

def test5():
	g = Graph(7)
	g.add(0, 1, 1)
	g.add(0, 2, 1)
	g.add(0, 3, 3)
	g.add(0, 5, 4)
	g.add(3, 4, 3)
	g.add(4, 6, 3)
	g.add(5, 6, 4)
	tree = dijkstra(g, 0)
	assert tree == [0, 0, 0, 0, 3, 0, 5], tree
	print('test 5 - YEAH')
(n, m) = [int(e) for e in input().strip().split(' ')]
g = Graph(n)
for _ in range(m):
	(v, w, vww) = [int(e) for e in input().strip().split(' ')]
	g.add(v - 1, w - 1, vww)
tree = dijkstra(g, 0)
if tree[n - 1] == None:
	print(-1)
else:
	x = n - 1
	ans = [x]
	while tree[x] != x:
		x = tree[x]
		ans.append(x)
	print(' '.join((str(x + 1) for x in reversed(ans))))


import heapq
(n, m) = map(int, input().split())
inf = 1 << 60
d = [[] for _ in range(n)]
b = [0] + [inf] * (n - 1)
c = [-1] * n
hist = [(0, 0)]
for i in range(m):
	(x, y, w) = map(int, input().split())
	d[x - 1].append((w, y - 1))
	d[y - 1].append((w, x - 1))
while hist:
	min_p = heapq.heappop(hist)
	min_ind = min_p[1]
	for p in d[min_ind]:
		(w, ind) = (b[min_ind] + p[0], p[1])
		if w < b[ind]:
			(b[ind], c[ind]) = (w, min_ind)
			heapq.heappush(hist, (w, ind))
if b[n - 1] == inf:
	print(-1)
else:
	(fin, path) = (n - 1, [])
	while fin != -1:
		path += [fin + 1]
		fin = c[fin]
	print(*path[::-1])


import heapq
import sys
import math

class priority_queue:

	def __init__(self):
		self.pq = []

	def push(self, item):
		heapq.heappush(self.pq, item)

	def pop(self):
		return heapq.heappop(self.pq)

	def empty(self):
		return len(self.pq) == 0

class DijkstraGraph:

	def __init__(self, n):
		self.adj = [[] for _ in range(n)]
		self.n = n

	def add_edge(self, u, v, w):
		self.adj[u - 1].append((v - 1, w))

	def dijkstra(self, source):
		s = source - 1
		dist = [math.inf] * self.n
		pred = [None] * self.n
		dist[s] = 0
		remaining = priority_queue()
		remaining.push((0, s))
		while not remaining.empty():
			(d, u) = remaining.pop()
			if d > dist[u]:
				continue
			for (v, w) in self.adj[u]:
				new_dist = d + w
				if new_dist < dist[v]:
					dist[v] = new_dist
					pred[v] = u
					remaining.push((new_dist, v))
		return (dist, pred)

	def get_path(self, u, pred):
		v = u - 1
		path = [v]
		if pred[v] is None:
			return [-1]
		while pred[v] != 0:
			path.append(pred[v])
			v = pred[v]
		path.append(pred[v])
		path = [x + 1 for x in path]
		return path[::-1]
(n, m) = map(int, input().split())
dijkstra = DijkstraGraph(n)
for i in range(m):
	(u, v, w) = map(int, input().split())
	dijkstra.add_edge(u, v, w)
	dijkstra.add_edge(v, u, w)
(dist, pred) = dijkstra.dijkstra(1)
path = dijkstra.get_path(n, pred)
for node in path:
	print(node, end=' ')


import math
import heapq
import sys
from collections import deque
import time
input = sys.stdin.readline
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(n, m) = invr()
d = {}
v = [0] * n
for i in range(1, n + 1):
	d[i] = []
for i in range(m):
	(a, b, w) = invr()
	d[a].append([b, w])
	d[b].append([a, w])
out = {}
c = {}
c[1] = 0
for i in range(2, n + 1):
	c[i] = float('inf')
queue = deque()
x = []
heapq.heappush(x, (0, 1, -1))
prev = -1
while True:
	a = heapq.heappop(x)
	s = a[1]
	if v[s - 1] == 1:
		continue
	v[s - 1] = 1
	c[s] = a[0]
	out[s] = a[2]
	if s == n:
		break
	for i in d[s]:
		if not v[i[0] - 1]:
			if a[0] + i[1] < c[i[0]]:
				heapq.heappush(x, (a[0] + i[1], i[0], s))
	if len(x) == 0:
		print(-1)
		exit()
a = []
x = n
while out[x] != -1:
	a.append(x)
	x = out[x]
a.append(1)
a.reverse()
print(*a)


from math import inf
from heapq import heappop, heappush

def dijkstra(graph, alpha):
	n = len(graph)
	distance = [inf] * n
	distance[alpha] = 0
	parents = [-1] * n
	queue = []
	heappush(queue, (0, alpha))
	while queue:
		(length, v) = heappop(queue)
		for (x, dist) in graph[v]:
			if dist + length < distance[x]:
				distance[x] = dist + length
				parents[x] = v
				heappush(queue, (dist + length, x))
	return (distance, parents)
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	graph = [[] for __ in range(n + 1)]
	for i in range(m):
		(x, y, w) = map(int, input().split())
		graph[x] += [(y, w)]
		graph[y] += [(x, w)]
	(hi, parents) = dijkstra(graph, 1)
	ans = [n]
	x = n
	while parents[x] != -1:
		ans += [parents[x]]
		x = parents[x]
	if ans and ans[-1] == 1:
		print(*ans[::-1])
	else:
		print(-1)


from heapq import *
INF = 1 << 60
(vertices, edges) = map(int, input().split())
graph = [[] for _ in range(vertices)]
distances = [0] + [INF] * vertices
visited = [-1] * vertices
priority_q = [(0, 0)]
for _ in range(edges):
	(start, end, weight) = map(int, input().split())
	graph[start - 1] += [(weight, end - 1)]
	graph[end - 1] += [(weight, start - 1)]
while priority_q:
	start = heappop(priority_q)[1]
	for item in graph[start]:
		temp = item[0] + distances[start]
		vertix = item[1]
		if temp < distances[vertix]:
			distances[vertix] = temp
			visited[vertix] = start
			heappush(priority_q, (temp, vertix))
if distances[vertices - 1] == INF:
	print(-1)
else:
	end = vertices - 1
	arr = []
	while end != -1:
		arr += [end + 1]
		end = visited[end]
	arr.reverse()
	print(' '.join(map(str, arr)))


(n, m) = map(int, input().split())
graph = {}
for _ in range(m):
	(a, b, w) = map(int, input().split())
	a -= 1
	b -= 1
	if a == b:
		continue
	l = graph.setdefault(a, {})
	l[b] = min([l.setdefault(b, w), w])
	l = graph.setdefault(b, {})
	l[a] = min([l.setdefault(a, w), w])
import heapq
(s, t) = (0, n - 1)
pq = [(0, s)]
inf = float('inf')
dist = [inf] * n
dist[0] = 0
p = [-1] * n
while len(pq) > 0:
	(d, v) = heapq.heappop(pq)
	if d > dist[v]:
		continue
	if v in graph:
		for (u, w) in graph[v].items():
			if dist[u] > w + d:
				dist[u] = w + d
				p[u] = v
				heapq.heappush(pq, (w + d, u))
if dist[t] == inf:
	print('-1')
else:
	v = t
	path = []
	while v >= 0:
		path.append(v + 1)
		v = p[v]
	print(' '.join([str(i) for i in path[::-1]]))


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'
from heapq import heappush, heappop, heapify
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for j in range(m):
	(a, b, w) = map(int, input().split())
	graph[a - 1].append([b - 1, w])
	graph[b - 1].append([a - 1, w])
inf = float('inf')
dist = {i: inf for i in range(1, n)}
dist[0] = 0
prec = {}
q = [(0, 0)]
while q:
	(d, node) = heappop(q)
	for (adj, w) in graph[node]:
		if d + w < dist[adj]:
			heappush(q, (d + w, adj))
			dist[adj] = d + w
			prec[adj] = node
i = n - 1
t = True
ans = [i + 1]
while i:
	if i in prec:
		ans.append(prec[i] + 1)
	else:
		t = False
		break
	i = prec[i]
if t:
	print(*ans[::-1])
else:
	print(-1)


import heapq

def read_nums():
	return map(lambda s: int(s), input().split(' '))

def shortest_path(graph, start, target):
	q = [(0, start, None)]
	seen = {}
	parents = {}
	while len(q) != 0:
		(dist, node, parent) = heapq.heappop(q)
		seendist = seen.get(node)
		if seendist is not None and seendist < dist:
			continue
		seen[node] = dist
		parents[node] = parent
		for (weight, neighbor) in graph.get(node, []):
			heapq.heappush(q, (dist + weight, neighbor, node))
	if target not in seen:
		print(-1)
		return
	else:
		path = []
		n = target
		while n:
			path.append(str(n))
			n = parents.get(n)
		path.reverse()
		print(' '.join(path))

def main():
	(n, m) = read_nums()
	graph = {}
	for _ in range(m):
		(u, v, w) = read_nums()
		graph.setdefault(u, []).append((w, v))
		graph.setdefault(v, []).append((w, u))
	shortest_path(graph, 1, n)
main()


import sys, heapq

class Queue(object):

	def __init__(self):
		self.heap = []

	def isEmpty(self):
		return len(self.heap) == 0

	def push(self, item):
		heapq.heappush(self.heap, item)

	def pop(self):
		return heapq.heappop(self.heap)

def dijkstra(s, adj_list):
	visited = [False] * len(adj_list)
	pred = [-1 for i in range(len(adj_list))]
	dist = [1000000000000.0 for i in range(len(adj_list))]
	remaining = Queue()
	dist[s] = 0
	remaining.push((0, s))
	while not remaining.isEmpty():
		(d, x) = remaining.pop()
		if visited[x]:
			continue
		visited[x] = True
		for (v, w) in adj_list[x]:
			if dist[v] > dist[x] + w:
				dist[v] = dist[x] + w
				pred[v] = x
				remaining.push((dist[v], v))
	return (dist, pred)

def construct_path(n, pred):
	path = []
	node = n
	if pred[node] == -1:
		return []
	while node != -1:
		path.append(node)
		node = pred[node]
	path.reverse()
	return path
(n, m) = list(map(int, input().split()))
adj_list = [[] for i in range(n + 1)]
for i in range(m):
	(x, y, w) = list(map(int, input().split()))
	adj_list[x].append((y, w))
	adj_list[y].append((x, w))
(dist, pred) = dijkstra(1, adj_list)
path = construct_path(n, pred)
if len(path) != 0:
	for i in range(len(path)):
		print(path[i], end=' ')
else:
	print(-1)


import collections, heapq
sol = False
params = [int(x) for x in input().split(' ')]
e = collections.defaultdict(dict)
for i in range(params[1]):
	edge = [int(x) for x in input().split(' ')]
	if edge[0] == edge[1]:
		continue
	if edge[1] in e[edge[0]] and edge[2] > e[edge[0]][edge[1]]:
		continue
	e[edge[0]][edge[1]] = edge[2]
	e[edge[1]][edge[0]] = edge[2]
if params[0] not in e:
	print(-1)
else:
	distances = {}
	distances[1] = (0, 0)
	pq = [(0, 1)]
	while len(pq) > 0:
		(currd, currv) = heapq.heappop(pq)
		if currv == params[0]:
			path = collections.deque([])
			while currv != 0:
				path.appendleft(currv)
				currv = distances[currv][1]
			print(' '.join((str(name) for name in path)))
			sol = True
			break
		if currd == distances[currv][0]:
			for (neigh, time) in e[currv].items():
				dist = currd + time
				if neigh not in distances or dist < distances[neigh][0]:
					distances[neigh] = (dist, currv)
					heapq.heappush(pq, (dist, neigh))
	if not sol:
		print(-1)


import sys
from heapq import heappush, heappop
push = lambda pq, node: heappush(pq, (node[1], node[0], node[2]))
pop = lambda pq: heappop(pq)
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
adj = {x + 1: dict() for x in range(n)}
for i in range(m):
	(a, b, w) = map(int, input().split())
	adj[a][b] = w
	adj[b][a] = w
infinity = 10 ** 15
distance = [infinity for _ in range(n + 1)]
distance[1] = 0
pq = []
push(pq, (1, distance[1], -1))
backpointer = {x: -1 for x in range(n + 1)}

def print_parent(backpointer, v):
	path = []
	while v != -1:
		path.append(str(v))
		v = backpointer[v]
	return ' '.join(reversed(path))
while pq:
	(cost, u, parent) = pop(pq)
	if u == n:
		print(print_parent(backpointer, u))
		break
	for v in adj[u]:
		if cost + adj[u][v] < distance[v]:
			distance[v] = cost + adj[u][v]
			push(pq, (v, distance[v], u))
			backpointer[v] = u
else:
	print(-1)


import heapq
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def dijkstra(source, neigh, dic):
	n = len(neigh)
	visited = [False] * n
	distance = [float('inf')] * n
	lastpath = [-1 for i in range(n)]
	distance[source] = 0
	heap = []
	heapq.heappush(heap, (0, source))
	while heap:
		temp = heapq.heappop(heap)
		(d, index) = (temp[0], temp[1])
		if visited[index]:
			continue
		visited[index] = True
		for ele in neigh[index]:
			if visited[ele]:
				continue
			newdistance = distance[index] + dic[index, ele]
			if newdistance >= distance[ele]:
				continue
			heapq.heappush(heap, (newdistance, ele))
			distance[ele] = newdistance
			lastpath[ele] = index
	return lastpath
(n, m) = map(int, input().split())
neigh = [[] for i in range(n)]
dic = {}
for e in range(m):
	(u, v, d) = map(int, input().split())
	neigh[u - 1].append(v - 1)
	neigh[v - 1].append(u - 1)
	dic[u - 1, v - 1] = d
	dic[v - 1, u - 1] = d
lastpath = dijkstra(0, neigh, dic)
if lastpath[-1] == -1:
	print(-1)
	exit(0)
ans = []
index = n - 1
while index != 0:
	ans.append(index + 1)
	index = lastpath[index]
ans.append(1)
print(' '.join(map(str, ans[::-1])))


import itertools
from heapq import heappush, heappop
pq = []
entry_finder = {}
REMOVED = '<removed-task>'
counter = itertools.count()

def put(task, priority=0):
	if task in entry_finder:
		remove_task(task)
	count = next(counter)
	entry = [priority, count, task]
	entry_finder[task] = entry
	heappush(pq, entry)

def remove_task(task):
	entry = entry_finder.pop(task)
	entry[-1] = REMOVED

def get():
	while pq:
		(priority, count, task) = heappop(pq)
		if task is not REMOVED:
			del entry_finder[task]
			return (priority, task)
	raise KeyError('pop from an empty priority queue')

def print_arr(arr):
	l = len(arr)
	for i in range(l - 1, 0, -1):
		print(arr[i], end=' ')
	print(arr[0])

class Node:

	def __init__(self, idx):
		self.visited = False
		self.prev = -1
		self.index = idx
		self.adj = []

class Task(object):

	def __init__(self, node, prev):
		(self.node, self.prev) = (node, prev)

def main():
	(num_node, num_edge) = input().split()
	(num_node, num_edge) = (int(num_node), int(num_edge))
	cost_list = dict()
	nodes = {}
	for i in range(1, num_node + 1):
		nodes[i] = Node(i)
	for i in range(num_edge):
		(u, v, c) = input().split()
		(u, v, c) = (int(u), int(v), int(c))
		nodes[u].adj.append(nodes[v])
		nodes[v].adj.append(nodes[u])
		idx1 = (u, v)
		idx2 = (v, u)
		if idx1 not in cost_list:
			cost_list[idx1] = c
			cost_list[idx2] = c
		else:
			cost_list[idx1] = c
			cost_list[idx2] = c
	put(Task(nodes[1], -1), 0)
	output = []
	while pq:
		(cost, out) = get()
		(node, prev) = (out.node, out.prev)
		if node.index == num_node:
			node.prev = prev
			while node.prev != -1:
				output.append(node.index)
				node = node.prev
			output.append(1)
			print_arr(output)
			return
		if node.visited:
			continue
		node.visited = True
		node.prev = prev
		for n in node.adj:
			if not n.visited:
				put(Task(n, node), cost + cost_list[node.index, n.index])
	print('-1')
main()


import os
import sys
if os.path.exists('C:\\Users\\User\\codeforces'):
	f = iter(open('A.txt').readlines())

	def input():
		return next(f).strip()
else:
	input = lambda : sys.stdin.readline().strip()
fprint = lambda *args: print(*args, flush=True)
import heapq
(n, m) = map(int, input().split())
g = {i: [] for i in range(n + 1)}
for i in range(m):
	(a, b, w) = map(int, input().split())
	g[a].append((b, w))
	g[b].append((a, w))
t = {i: [] for i in range(n + 1)}
M = 10 ** 18
color = [0] * (n + 1)
weight = [M] * (n + 1)
weight[1] = 0
stack = [(0, 1)]
while stack:
	(_, cur) = heapq.heappop(stack)
	if color[cur] != 0:
		continue
	w_cur = weight[cur]
	for (to, w_to) in g[cur]:
		weight[to] = min(weight[to], w_cur + w_to)
		heapq.heappush(stack, (weight[to], to))
	color[cur] = 1
for cur in g:
	for (to, w_to) in g[cur]:
		if weight[to] == weight[cur] + w_to:
			t[cur].append(to)
			t[to].append(cur)
if weight[n] == M:
	print(-1)
else:
	dist = [M] * (n + 1)
	dist[1] = 0
	stack = [1]
	color = [0] * (n + 1)
	while stack:
		cur = stack[0]
		stack = stack[1:]
		if color[cur] != 0:
			continue
		d_cur = dist[cur]
		for to in t[cur]:
			dist[to] = min(dist[to], d_cur + 1)
			stack.append(to)
		color[cur] = 1
	cur = n
	path = [cur]
	while cur != 1:
		for to in t[cur]:
			if dist[cur] == dist[to] + 1:
				cur = to
				path.append(to)
				break
	print(' '.join(map(str, reversed(path))))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def ctd(chr):
	return ord(chr) - ord('a')
mod = 998244353
INF = float('inf')
from heapq import heappushpop, heappush

def main():
	(n, m) = RL()
	gp = defaultdict(dict)
	for _ in range(m):
		(f, t, w) = RL()
		gp[f][t] = w
		gp[t][f] = w
	q = []
	heappush(q, (0, 1))
	vis = [0] * (n + 1)
	par = [-1] * (n + 1)
	darr = [INF] * (n + 1)
	darr[1] = 0
	while q:
		(d, nd) = heappop(q)
		vis[nd] = 1
		for nex in gp[nd]:
			if vis[nex] == 1:
				continue
			dis = gp[nd][nex] + darr[nd]
			if dis < darr[nex]:
				darr[nex] = dis
				par[nex] = nd
				heappush(q, (dis, nex))
	res = [n]
	while par[res[-1]] != -1:
		res.append(par[res[-1]])
	if par[n] == -1:
		print(-1)
	else:
		print(*res[::-1])
main()


from collections import deque
from heapq import *
from sys import stdin
(V, E) = map(int, stdin.readline().rstrip().split())
adj_list = []
shortest_paths = []
for v in range(0, V):
	adj_list.append([])
for e in range(0, E):
	(v1, v2, length) = map(int, stdin.readline().rstrip().split())
	adj_list[v1 - 1].append((v2 - 1, length))
	adj_list[v2 - 1].append((v1 - 1, length))

def dijkstra(start, end):
	heapq = [(0, start)]
	seen = [False] * V
	shortest_dist = [100000000000] * V
	shortest_dist[0] = 0
	predecessors = [-1] * V
	predecessors[0] = 0
	while heapq:
		(dist, v1) = heappop(heapq)
		if not seen[v1]:
			seen[v1] = True
			if v1 == end:
				return (dist, predecessors)
			for (v2, length) in adj_list[v1]:
				if not seen[v2]:
					new_dist = dist + length
					if new_dist < shortest_dist[v2]:
						shortest_dist[v2] = new_dist
						predecessors[v2] = v1
						heappush(heapq, (new_dist, v2))
	return ()
result = dijkstra(0, V - 1)
if result:
	predecessors = result[1]
	path = deque()
	node = V - 1
	while not node == 0:
		path.appendleft(node + 1)
		node = predecessors[node]
	path.appendleft(1)
	print(*path)
else:
	print(-1)


from heapq import heappop, heappush
from sys import stdin

class node:

	def __init__(self, vertex, distance):
		self.vertex = vertex
		self.distance = distance

	def __lt__(self, rhs):
		return self.distance < rhs.distance

def make_graph(m):
	graph_dict = {}
	for _ in range(m):
		s = input()
		(from_vertex, to_vertex, distance) = (int(t) for t in s.split())
		if from_vertex not in graph_dict:
			graph_dict[from_vertex] = {}
		if to_vertex not in graph_dict:
			graph_dict[to_vertex] = {}
		graph_dict[from_vertex][to_vertex] = distance
		graph_dict[to_vertex][from_vertex] = distance
	return graph_dict

def find_path(graph_dict, begin_vertex, end_vertex):
	end_node = node(end_vertex, 0)
	node_dict = {end_vertex: end_node}
	queue = []
	heappush(queue, end_node)
	while queue:
		from_node = heappop(queue)
		from_vertex = from_node.vertex
		from_distance = from_node.distance
		if from_vertex == begin_vertex:
			return node_dict
		if from_vertex in graph_dict:
			for to_vertex in graph_dict[from_vertex]:
				distance = from_distance + graph_dict[from_vertex][to_vertex]
				if to_vertex not in node_dict or distance < node_dict[to_vertex].distance:
					node_dict[to_vertex] = node(from_vertex, distance)
					heappush(queue, node(to_vertex, distance))
	return {}

def test_case(n, m):
	begin_vertex = 1
	end_vertex = n
	graph_dict = make_graph(m)
	node_dict = find_path(graph_dict, begin_vertex, end_vertex)
	if not node_dict:
		print('-1')
		return
	path_list = [begin_vertex]
	while begin_vertex != end_vertex:
		begin_vertex = node_dict[begin_vertex].vertex
		path_list.append(begin_vertex)
	print(' '.join((str(v) for v in path_list)))

def main():
	for s in stdin:
		(n, m) = (int(t) for t in s.split())
		test_case(n, m)
main()


import sys
import heapq
from sys import stdin, stdout
(n, m) = [int(x) for x in stdin.readline().split()]
inizio = 0
fine = n - 1
grafo = []
dist = []
dist_massima = 1
for i in range(n):
	grafo.append([])
for i in range(m):
	(da, a, peso) = [int(x) for x in stdin.readline().split()]
	da = da - 1
	a = a - 1
	dist_massima = dist_massima + peso
	grafo[da].append([peso, a, False])
	grafo[a].append([peso, da, False])
for i in range(n):
	grafo[i].sort()
	dist.append(dist_massima)
dist[inizio] = 0
h = []
count = 1
heapq.heappush(h, (0, inizio, -1))
sol = []
completato = False
while count != 0 and (not completato):
	gianni = heapq.heappop(h)
	count = count - 1
	if gianni[1] == n - 1:
		completato = True
		sol.append(gianni)
	elif gianni[0] == dist[gianni[1]]:
		sol.append(gianni)
		for adj in grafo[gianni[1]]:
			if adj[0] + gianni[0] < dist[adj[1]]:
				count = count + 1
				dist[adj[1]] = adj[0] + gianni[0]
				heapq.heappush(h, (dist[adj[1]], adj[1], len(sol) - 1))
if not completato:
	stdout.write('-1')
else:
	index = len(sol) - 1
	soluzioni = []
	while index != -1:
		soluzioni.append(sol[index][1])
		index = sol[index][2]
	lunghezza_lista = len(soluzioni)
	for i in range(lunghezza_lista):
		stdout.write(str(soluzioni[lunghezza_lista - 1 - i] + 1) + ' ')


import queue
import heapq

class Graph:

	def __init__(self, verts):
		self.adj = []
		for _ in range(verts):
			self.adj.append([])

	def __len__(self):
		return len(self.adj)

	def addEdge(self, a, b, weight):
		self.adj[a].append((b, weight))
		self.adj[b].append((a, weight))

	def getNodes(self):
		return [i for i in range(len(self.adj))]

	def getNodeWeights(self):
		pass

	def getNeigh(self, a):
		return [i[0] for i in self.adj[a]]

	def getNeighW(self, a):
		return self.adj[a]

def bfs(g, source):
	queue = []
	dist = [99999] * len(g)
	pred = [-1] * len(g)
	visited = [False] * len(g)
	queue.append(source)
	dist[source] = 0
	visited[source] = True
	while len(queue) > 0:
		thisNode = queue.pop(0)
		for n in g.getNeigh(thisNode):
			if visited[n] == False:
				dist[n] = dist[thisNode] + 1
				pred[n] = thisNode
				queue.append(n)
				visited[n] = True
	print(dist)
	return [i for i in dist]

def dijkstra(g, source):
	removed = []
	INFINITY = int(1000000000000.0)
	dist = [INFINITY] * len(g)
	pred = [-1] * len(g)
	remaining = []
	dist[source] = 0
	heapq.heappush(remaining, (0, source))
	while len(remaining) > 0:
		(ww, x) = heapq.heappop(remaining)
		if ww == INFINITY:
			continue
		for y in g.getNeighW(x):
			est = dist[x] + y[1]
			if est < dist[y[0]]:
				dist[y[0]] = est
				heapq.heappush(remaining, (est, y[0]))
				pred[y[0]] = x
	return (dist, pred)
header = input()
header = [int(i) for i in header.split()]
nodes = header[0]
edges = header[1]
g = Graph(nodes + 1)
for _ in range(edges):
	edgeData = input()
	edgeData = [int(i) for i in edgeData.split()]
	g.addEdge(edgeData[0], edgeData[1], edgeData[2])
paths = dijkstra(g, 1)
pred = paths[1]
ans = []
current = nodes
nopath = False
while current != -1:
	ans.append(current)
	current = pred[current]
if ans[-1] == 1:
	print(' '.join([str(i) for i in ans[::-1]]))
else:
	print(-1)


from heapq import heappop, heappush
(V, A) = map(int, input().split(' '))
graph = [[] for i in range(V + 1)]
for i in range(A):
	(inicio, fim, peso) = map(int, input().split(' '))
	graph[inicio].append((peso, fim))
	graph[fim].append((peso, inicio))
heap = [(0, 1)]
pai = [0] * (V + 1)
custo = [float('inf')] * (V + 1)
custo[1] = 0
while len(heap) > 0:
	(peso, inicio) = heappop(heap)
	for (w, fim) in graph[inicio]:
		if custo[fim] > peso + w:
			pai[fim] = inicio
			custo[fim] = peso + w
			heappush(heap, (peso + w, fim))
if pai[V] != 0:
	saida = []
	m = V
	while True:
		saida.append(m)
		if m == 1:
			break
		m = pai[m]
	print(' '.join(map(str, reversed(saida))))
else:
	print(-1)


import sys
from sys import stdin, stdout
from heapq import *
st = lambda : list(stdin.readline().strip())
li = lambda : list(map(int, stdin.readline().split()))
mp = lambda : map(int, stdin.readline().split())
inp = lambda : int(stdin.readline())
pr = lambda n: stdout.write(str(n) + '\n')
INF = float('inf')
(n, m) = mp()
d = {i: [] for i in range(1, n + 1)}
for i in range(m):
	(a, b, c) = mp()
	d[a].append((b, c))
	d[b].append((a, c))
dis = [INF for i in range(n + 1)]
dis[1] = 0
h = []
heappush(h, (0, 1))
v = [False for i in range(n + 1)]
par = [-1 for i in range(n + 1)]
while h:
	(cur_dis, cur_node) = heappop(h)
	if v[cur_node]:
		continue
	v[cur_node] = True
	for (node, distance) in d[cur_node]:
		if cur_dis + distance < dis[node]:
			dis[node] = cur_dis + distance
			heappush(h, (dis[node], node))
			par[node] = cur_node
if not v[n]:
	pr(-1)
else:
	ans = []
	ans.append(n)
	n = par[n]
	while par[n] > 0:
		ans.append(n)
		n = par[n]
	ans.append(1)
	print(*reversed(ans))


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'
import heapq

def solve():
	(n, m) = map(int, input().split())
	edge_list = {x: [] for x in range(1, n + 1)}
	for i in range(m):
		st = input().split()
		if not st:
			break
		(a, b, w) = map(int, st)
		edge_list[a].append((b, w))
		edge_list[b].append((a, w))
	dist = [float('inf')] * (n + 1)
	hq = [(0, 1)]
	dist[1] = 0
	visited = [False] * (n + 1)
	path = [-1] * (n + 1)
	while hq:
		ele = heapq.heappop(hq)
		if visited[ele[1]]:
			continue
		visited[ele[1]] = True
		for edge in edge_list[ele[1]]:
			if dist[ele[1]] + edge[1] < dist[edge[0]]:
				dist[edge[0]] = dist[ele[1]] + edge[1]
				path[edge[0]] = ele[1]
				heapq.heappush(hq, (dist[edge[0]], edge[0]))
	st = n
	pt = []
	while st >= 1 and dist[st] < float('inf'):
		pt.append(st)
		st = path[st]
	if dist[st] == float('inf'):
		cout << -1
		return
	cout << ' '.join(map(str, pt[::-1]))

def main():
	solve()
main()


import sys
input = sys.stdin.readline
from math import inf
from heapq import heappop, heappush
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b, w) = map(int, input().split())
	graph[a].append((b, w))
	graph[b].append((a, w))
(heap, dist, parent) = ([(0, 1)], [inf] * (n + 1), [0] * (n + 1))
while heap:
	(d, vertex) = heappop(heap)
	for (child, weight) in graph[vertex]:
		weight += d
		if dist[child] > weight:
			dist[child] = weight
			parent[child] = vertex
			heappush(heap, (weight, child))
if not parent[n]:
	print(-1)
	exit()
(ans, node) = ([n], n)
while node != 1:
	node = parent[node]
	ans.append(node)
ans.reverse()
print(' '.join(map(str, ans)))


__author__ = '\n\n\n   ***   \t           *\n    *                  *\n    *                  *\n    *\t ****\t ****  *****    ****   *   *\n    *\t*   *   *      *   *    *  *   *   *   \n    *\t*   *   *      *   *    *  *   *   *\n*   *\t*   *   *      *   *    *  *   *****      \n*   *\t*   *   *      *   *    *  *       *  \n ***\t *** *  *      *****    *** *      * \n                                           *\n********************************************  \n'
from math import inf
import heapq as h
from sys import stdin, stdout
(n, m) = map(int, input().split())
g = []
pred = []
visited = []
dist = []
for i in range(n):
	g.append([])
	pred.append(None)
	visited.append(0)
	dist.append(inf)
dist[0] = 0

def dijkstra():
	stack = [[0, 0]]
	while stack:
		v = h.heappop(stack)[1]
		if v == n - 1:
			break
		if visited[v] == 0:
			visited[v] = 1
			for (node, cost) in g[v]:
				if visited[node] == 1:
					continue
				if dist[v] + cost < dist[node]:
					dist[node] = dist[v] + cost
					pred[node] = v
					h.heappush(stack, [dist[node], node])
for i in range(m):
	(a, b, cost) = [int(x) for x in stdin.readline().rstrip().split()]
	g[a - 1].append((b - 1, cost))
	g[b - 1].append((a - 1, cost))
dijkstra()
if pred[-1] is None:
	print(-1)
else:
	path = [n]
	while pred[path[-1] - 1] is not None:
		path.append(pred[path[-1] - 1] + 1)
	print(*path[::-1])


import sys
import heapq
INF = 1 << 60
(V, E) = map(int, input().strip().split())
adj = [[] for _ in range(V + 1)]
for _ in range(E):
	(u, v, w) = map(int, input().strip().split())
	adj[u].append((v, w))
	adj[v].append((u, w))
dist = [INF] * (V + 1)
mark = [0] * (V + 1)
dist[1] = 0
heap = [(dist[1], 1)]
prev = [0] * (V + 1)
while heap:
	(d, node) = heapq.heappop(heap)
	if mark[node]:
		continue
	mark[node] = 1
	if node == V:
		break
	for (nei, w) in adj[node]:
		if dist[node] + w < dist[nei]:
			dist[nei] = dist[node] + w
			prev[nei] = node
			heapq.heappush(heap, (dist[nei], nei))
if not mark[V]:
	exit(print(-1))
else:
	p = V
	ans = []
	while p != 0:
		ans.append(str(p))
		p = prev[p]
	print(' '.join(ans[::-1]))


from heapq import heappush, heappop
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
previous = [False] * (n + 1)
distance = [0] + [float('inf')] * n
heap = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	graph[a].append((b, c))
	graph[b].append((a, c))
heappush(heap, (0, 1, False))
while heap:
	(cost, node, prev) = heappop(heap)
	if visited[node]:
		continue
	visited[node] = True
	previous[node] = prev
	for (adj, weight) in graph[node]:
		if not visited[adj] and cost + weight < distance[adj]:
			heappush(heap, (cost + weight, adj, node))
path = []
node = n
while node:
	path.append(node)
	node = previous[node]
if len(path) > 1:
	print(' '.join(map(str, reversed(path))))
else:
	print(-1)


from heapq import heappop, heappush
(nodes, edges) = map(int, input().split())
adj = [dict() for i in range(nodes + 1)]
prev = [None] * (nodes + 1)
visited = [False] * (nodes + 1)
costList = [float('inf')] * (nodes + 1)
for i in range(edges):
	(start, end, dist) = map(int, input().split())
	adj[start][end] = min(adj[start].get(end, float('inf')), dist)
	adj[end][start] = adj[start][end]
pq = []
counter = 0
heappush(pq, (0, counter, 1))
counter += 1
while pq:
	(cost, count, index) = heappop(pq)
	if index == nodes:
		break
	if not visited[index]:
		visited[index] = True
		for (nextIndex, nextCost) in adj[index].items():
			if cost + nextCost < costList[nextIndex]:
				costList[nextIndex] = cost + nextCost
				prev[nextIndex] = index
				heappush(pq, (cost + nextCost, counter, nextIndex))
				counter += 1
res = []
backIndex = nodes
while backIndex != 1:
	if backIndex == None:
		print(-1)
		exit(0)
	res.append(backIndex)
	backIndex = prev[backIndex]
res.append(backIndex)
res.reverse()
print(*res)


from heapq import heappop, heappush
import sys
input = sys.stdin.readline
inf = 10 ** 18

def dijstkra(source):
	distance = [inf] * (n + 1)
	queue = [(0, source)]
	distance[source] = 0
	while queue:
		(l, u) = heappop(queue)
		for (v, w) in graph[u]:
			if distance[u] + w < distance[v]:
				distance[v] = distance[u] + w
				previous_node[v] = u
				heappush(queue, (distance[v], v))
(n, m) = map(int, input().split())
graph = [[] for _ in range(1 + n)]
previous_node = [-1] * (n + 1)
for _ in range(m):
	(u, v, w) = map(int, input().split())
	graph[u].append((v, w))
	graph[v].append((u, w))
dijstkra(1)
destination = n
path = [n]
state = True
while destination != 1 and state:
	if previous_node[destination] == -1:
		state = False
	path.append(previous_node[destination])
	destination = previous_node[destination]
	if destination == 1:
		break
if state:
	print(*path[::-1])
else:
	print(-1)


import heapq

def dijkstra(graph, s, t):
	prevMap = {}
	q = []
	q.append((0, s, -1))
	while len(q) > 0:
		(l, curr, prev) = heapq.heappop(q)
		if curr in prevMap:
			continue
		prevMap[curr] = prev
		if curr == t:
			ans = []
			while curr != -1:
				ans.append(str(curr))
				curr = prevMap[curr]
			ans = ans[::-1]
			return ' '.join(ans)
		for v in graph[curr].keys():
			if v not in prevMap:
				heapq.heappush(q, (l + graph[curr][v], v, curr))
	return '-1'
(n, m) = (int(x) for x in input().split())
graph = {}
for i in range(1, n + 1):
	graph[i] = {}
for _ in range(m):
	(a, b, w) = (int(x) for x in input().split())
	if a != b:
		graph[a][b] = min(graph[a].get(b, float('inf')), w)
		graph[b][a] = min(graph[b].get(a, float('inf')), w)
print(dijkstra(graph, 1, n))


from heapq import heappush, heappop
(n, m) = map(int, input().split())
graph = []
for i in range(n + 1):
	graph.append([])
for _ in range(m):
	(begin, end, weight) = map(int, input().split())
	graph[begin].append((end, weight))
	graph[end].append((begin, weight))
h = [(0, 1)]
costs = [float('inf')] * (n + 1)
parent = [0] * (n + 1)
while h:
	(cost, begin) = heappop(h)
	for (end, weight) in graph[begin]:
		weight += cost
		if costs[end] > weight:
			parent[end] = begin
			costs[end] = weight
			heappush(h, (weight, end))
if not parent[n]:
	print(-1)
else:
	res = [n]
	while n != 1:
		n = parent[n]
		res.append(n)
	res.reverse()
	print(' '.join(map(str, res)))


import sys
import heapq

def readInts():
	return [int(x) for x in sys.stdin.readline().split()]

def readInt():
	return int(sys.stdin.readline())

def solve():
	(n, m) = readInts()
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(u, v, w) = readInts()
		u -= 1
		v -= 1
		adj[u].append((v, w))
		adj[v].append((u, w))
	INF = int(1e+18)
	d = [INF] * n
	p = [-1] * n
	s = 0
	d[s] = 0
	q = [(0, s)]
	while len(q) > 0:
		pair1 = heapq.heappop(q)
		u = pair1[1]
		du = pair1[0]
		if du != d[u]:
			continue
		for pair2 in adj[u]:
			v = pair2[0]
			w = pair2[1]
			if d[u] + w < d[v]:
				d[v] = d[u] + w
				p[v] = u
				heapq.heappush(q, (d[v], v))
	if d[n - 1] == INF:
		print(-1)
	else:
		cur = n - 1
		ans = []
		while cur != -1:
			ans.append(cur)
			cur = p[cur]
		ans.reverse()
		ans = [x + 1 for x in ans]
		print(*ans, ' ')

def main():
	t = 1
	for _ in range(t):
		solve()
main()


import sys
from collections import defaultdict
import heapq
input = sys.stdin.readline

def get_adj_mat(src, dst, weight):
	matrix = defaultdict(list)
	for (src_i, dst_i, weight_i) in zip(src, dst, weight):
		matrix[src_i].append((weight_i, dst_i))
		matrix[dst_i].append((weight_i, src_i))
	return matrix

def dikjstra(root, destination, adj_mat, n):
	costs = [-1] * n
	back = [-1] * n
	root_cost = 0
	min_queue = []
	heapq.heappush(min_queue, (root_cost, -1, root))
	while min_queue:
		(src_cost, src_edge_par, src_edge) = heapq.heappop(min_queue)
		if costs[src_edge] == -1:
			costs[src_edge] = src_cost
			back[src_edge] = src_edge_par
			if src_edge == destination:
				break
			for (dst_cost, dst_edge) in adj_mat[src_edge]:
				if costs[dst_edge] == -1:
					heapq.heappush(min_queue, (src_cost + dst_cost, src_edge, dst_edge))
	if costs[destination] == -1:
		return [-1]
	else:
		pos = destination
		ans = [pos + 1]
		while pos > 0:
			ans.append(back[pos] + 1)
			pos = back[pos]
		return ans[::-1]

def solve(src, dst, weight, n):
	adj_mat = get_adj_mat(src, dst, weight)
	print(*dikjstra(0, n - 1, adj_mat, n))
(n, m) = [int(val) for val in input().split()]
(src, dst, weight) = ([], [], [])
for _ in range(m):
	(src_i, dst_i, weight_i) = [int(val) for val in input().split()]
	(src.append(src_i - 1), dst.append(dst_i - 1), weight.append(weight_i))
solve(src, dst, weight, n)


import heapq
import collections
from sys import stdin, stdout
input = stdin.readline

def dijkstra(adjacency_list, src, v):
	pred = {i: i for i in adjacency_list}
	dist = {i: 'x' for i in range(v + 1)}
	minHeap = []
	dist[src] = 0
	heapq.heappush(minHeap, [dist[src], src])
	while minHeap:
		first = heapq.heappop(minHeap)
		first_dist = first[0]
		first_vertex = first[1]
		if first_dist == dist[first_vertex]:
			for i in adjacency_list[first_vertex]:
				i_vertex = i[0]
				i_weight = i[1]
				if dist[i_vertex] == 'x':
					dist[i_vertex] = dist[first_vertex] + i_weight
					heapq.heappush(minHeap, [dist[i_vertex], i_vertex])
					pred[i_vertex] = first_vertex
				elif dist[first_vertex] + i_weight < dist[i_vertex]:
					dist[i_vertex] = dist[first_vertex] + i_weight
					heapq.heappush(minHeap, [dist[i_vertex], i_vertex])
					pred[i_vertex] = first_vertex
	return (dist, pred)
(n, m) = map(int, input().split())
d = collections.defaultdict(list)
for _ in range(m):
	(a, b, w) = map(int, input().split())
	d[a].append([b, w])
	d[b].append([a, w])
z = dijkstra(d, 1, n)
dist = z[0]
pred = z[1]
if dist[n] == 'x':
	print(-1)
else:
	ans = []
	ans.append(n)
	while ans[-1] != 1:
		ans.append(pred[ans[-1]])
	ans = ans[::-1]
	print(*ans)


import heapq as heap

def path(parent, n):
	li = []
	curr = n
	while curr != -1:
		li.append(curr)
		curr = parent[curr]
	li.reverse()
	return ' '.join(map(str, li))

def dijkstra(g, s, n):
	dis = [float('infinity') for i in range(n + 1)]
	vis = dict()
	dis[s] = 0
	parent = {1: -1}
	q = [(0, s)]
	while len(q) > 0:
		(_, x) = heap.heappop(q)
		if x in vis:
			continue
		vis[x] = True
		for (y, w) in g[x].items():
			if dis[x] + w < dis[y]:
				heap.heappush(q, (dis[x] + w, y))
				dis[y] = dis[x] + w
				parent[y] = x
	if dis[n] == float('inf'):
		return -1
	return path(parent, n)
(n, m) = map(int, input().split())
g = [{} for _ in range(n + 1)]
for _ in range(m):
	(x, y, z) = map(int, input().split())
	g[x][y] = z
	g[y][x] = z
print(dijkstra(g, 1, n))