NIKKEI Programming Contest 2019-2 - Shortest Path on a Line

We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices. In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph. The i-th operation is as follows:

* The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i. For every pair of integers (s, t) such that L_i \leq s < t \leq R_i, add an edge of length C_i between Vertex s and Vertex t.



The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq L_i < R_i \leq N
* 1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N M
L_1 R_1 C_1
:
L_M R_M C_M


Output

Print the length of the shortest path from Vertex 1 to Vertex N in the final graph. If there is no shortest path, print `-1` instead.

Examples

Input

4 3
1 3 2
2 4 3
1 4 6


Output

5


Input

4 2
1 2 1
3 4 2


Output

-1


Input

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3


Output

28

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from heapq import heappush, heappop
(N, M) = map(int, input().split())
LRC = [list(map(int, input().split())) for i in range(M)]
data = [[], []] + [[[i - 1, 0]] for i in range(2, N + 1)]
for (L, R, C) in LRC:
	data[L].append([R, C])
dist = [[0, 1]]
inf = float('inf')
flag = [inf] * (N + 1)
while dist:
	(y, x) = heappop(dist)
	if flag[x] != inf:
		continue
	flag[x] = y
	for u in data[x]:
		if flag[u[0]] == inf:
			heappush(dist, [y + u[1], u[0]])
	if flag[N] != inf:
		break
if flag[N] == inf:
	print(-1)
else:
	print(flag[N])


INF = 1e+16
(N, M) = map(int, input().split())
LRC = [tuple(map(int, input().split())) for _ in range(M)]
LRC.sort()
dp = [INF] * N
dp[0] = 0
for (l, r, c) in LRC:
	l -= 1
	r -= 1
	if dp[l] == INF:
		continue
	for i in range(r, l, -1):
		if dp[i] > dp[l] + c:
			dp[i] = dp[l] + c
		else:
			break
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


import heapq
(n, m) = map(int, input().split())
to = [list() for _ in range(n)]
for i in range(m):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	to[l].append((r, c))
for i in range(1, n):
	to[i].append((i - 1, 0))
q = []
INF = 1001001001001001
d = [INF] * n
d[0] = 0
heapq.heappush(q, (0, 0))
while q:
	(cost, u) = heapq.heappop(q)
	if d[u] < cost:
		continue
	for (v, c) in to[u]:
		if d[v] > d[u] + c:
			d[v] = d[u] + c
			heapq.heappush(q, (d[v], v))
if d[-1] == INF:
	print(-1)
else:
	print(d[-1])


import heapq
(n, m) = map(int, input().split(' '))
edges = [[] for _ in range(n)]
for _ in range(m):
	(l, r, c) = map(int, input().split(' '))
	edges[l - 1].append((r - 1, c))
dists = [None for _ in range(n)]
h = [(0, 0)]
for i in range(n):
	while len(h) > 0 and h[0][1] < i:
		heapq.heappop(h)
	if len(h) == 0:
		break
	dists[i] = h[0][0]
	for e in edges[i]:
		heapq.heappush(h, (e[1] + dists[i], e[0]))
print(-1 if dists[i] is None else dists[-1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
E = []
for i in range(M):
	(L, R, C) = map(int, input().split())
	E.append([L - 1, R - 1, C])
E = sorted(E)
N_ = 2 ** (len(bin(N)) - 2)
INF = 10 ** 15
seg = [INF] * (2 * N_ - 1)

def update(k, a):
	k += N_ - 1
	seg[k] = a
	while k > 0:
		k = (k - 1) // 2
		seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2])

def query(a, b, k, l, r):
	if r <= a or b <= l:
		return INF
	if a <= l and r <= b:
		return seg[k]
	else:
		vl = query(a, b, k * 2 + 1, l, (l + r) // 2)
		vr = query(a, b, k * 2 + 2, (l + r) // 2, r)
		return min(vl, vr)
update(0, 0)
for i in range(M):
	new = query(E[i][0], E[i][1], 0, 0, N_) + E[i][2]
	if new < seg[E[i][1] + N_ - 1]:
		update(E[i][1], new)
if seg[N - 1 + N_ - 1] == INF:
	print(-1)
else:
	print(seg[N - 1 + N_ - 1])


import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

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

def read_index():
	return map(lambda x: int(x) - 1, input().split())

def read_list():
	return list(read_values())

def read_lists(N):
	return [read_list() for n in range(N)]

def main():
	(N, M) = read_values()
	T = read_lists(M)
	T.sort()
	S = []
	C = [10 ** 20] * N
	C[0] = 0
	t = 0
	for i in range(N):
		if i != 0 and len(S) == 0:
			print(-1)
			return
		(c, r) = (0, 0) if len(S) == 0 else S[0]
		while t < M:
			(ll, rr, cc) = T[t]
			ll -= 1
			rr -= 1
			if ll > i:
				break
			C[rr] = min(C[rr], c + cc)
			heapq.heappush(S, (C[rr], rr))
			t += 1
		while S:
			if S[0][1] > i:
				break
			heapq.heappop(S)
	print(C[-1])
main()


from heapq import heappush, heappop

def main():
	INF = float('inf')
	(N, M, *LRC) = map(int, open(0).read().split())
	E = [[] for _ in range(N)]
	for i in range(N - 1):
		E[i + 1].append((i, 0))
	for (l, r, c) in zip(*[iter(LRC)] * 3):
		E[l - 1].append((r - 1, c))
	D = [INF] * N
	D[0] = 0
	Q = [0]
	while Q:
		(dist, cur) = divmod(heappop(Q), N)
		for (nxt, cost) in E[cur]:
			cand = dist + cost
			if D[nxt] > cand:
				D[nxt] = cand
				heappush(Q, cand * N + nxt)
	print(-1 if D[N - 1] == INF else D[N - 1])
main()


import sys
input = sys.stdin.readline
import heapq

def dijkstra(start, edge):
	n = len(edge)
	dist = [float('inf')] * n
	dist[start] = 0
	que = [(0, start)]
	while que:
		(d, v) = heapq.heappop(que)
		if dist[v] < d:
			continue
		for (nv, nd) in edge[v]:
			if dist[nv] > d + nd:
				dist[nv] = d + nd
				heapq.heappush(que, (dist[nv], nv))
	return dist
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(1, n):
	G[i].append((i - 1, 0))
for _ in range(m):
	(l, r, c) = map(int, input().split())
	G[l - 1].append((r - 1, c))
D = dijkstra(0, G)
ans = D[n - 1]
if ans == float('inf'):
	ans = -1
print(ans)


import heapq
import sys
(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(l, r, c) = map(int, input().split())
	edges.append((l - 1, r - 1, c))
edges.sort(reverse=True)
dp = [0] * N
que = [(0, 0)]
for i in range(1, N):
	while len(edges) > 0 and edges[-1][0] == i - 1:
		e = edges.pop()
		heapq.heappush(que, (dp[i - 1] + e[2], e[1]))
	while True:
		if len(que) == 0:
			print(-1)
			sys.exit()
		e = heapq.heappop(que)
		if e[1] >= i:
			dp[i] = e[0]
			heapq.heappush(que, e)
			break
print(dp[-1])


from heapq import heappush, heappop

def dijkstra(s, n, dic):
	q = [(0, s)]
	dist = [10 ** 20] * n
	dist[s] = 0
	while q:
		(v, p) = heappop(q)
		if dist[p] < v:
			continue
		for (e, c) in dic[p]:
			if dist[e] > dist[p] + c:
				dist[e] = dist[p] + c
				heappush(q, (dist[e], e))
	return dist
(N, M, *L) = map(int, open(0).read().split())
Els = [[] for i in range(N + 1)]
for i in range(2, N + 1):
	Els[i].append((i - 1, 0))
for (l, r, c) in zip(*[iter(L)] * 3):
	Els[l].append((r, c))
dist = dijkstra(1, N + 1, Els)
if dist[N] == 10 ** 20:
	print(-1)
else:
	print(dist[N])


(N, M) = map(int, input().split())
import heapq

def dijkstra_heap(s):
	dist = [float('inf')] * size_v
	prev = [-1] * size_v
	used = [False] * size_v
	dist[s] = 0
	used[s] = True
	hq_edge = []
	for (v, w) in graph[s]:
		heapq.heappush(hq_edge, (w, v, s))
	while hq_edge:
		(min_w, min_v, u) = heapq.heappop(hq_edge)
		if used[min_v]:
			continue
		dist[min_v] = min_w
		prev[min_v] = u
		used[min_v] = True
		for (v, w) in graph[min_v]:
			if not used[v]:
				heapq.heappush(hq_edge, (min_w + w, v, min_v))
	return (dist, prev)
size_v = N + 1
s = 1
graph = [[] for _ in range(size_v)]
for i in range(2, N):
	graph[i].append((i - 1, 0))
for _ in range(M):
	(L, R, C) = map(int, input().split())
	graph[L].append((R, C))
(dist, prev) = dijkstra_heap(s)
if dist[N] == float('inf'):
	print(-1)
else:
	print(dist[N])


(N, M) = map(int, input().split())
LRC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: (x[0], x[1]))
inf = float('inf')
dp = [inf] * N
dp[0] = 0
for (l, r, c) in LRC:
	for i in range(r, l, -1):
		if dp[i - 1] > dp[l - 1] + c:
			dp[i - 1] = dp[l - 1] + c
		else:
			break
if dp[-1] < inf:
	print(dp[-1])
else:
	print(-1)


import sys
input = sys.stdin.readline
INF = 10 ** 15
(N, M) = map(int, input().split())
LRCs = [tuple(map(int, input().split())) for _ in range(M)]
LRCs.sort(key=lambda t: (t[1], t[0]))
dp = [INF] * N
dp[0] = 0
for (L, R, C) in LRCs:
	while dp[R - 1] > dp[L - 1] + C:
		dp[R - 1] = dp[L - 1] + C
		R -= 1
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


from heapq import heappush, heappop
(N, M) = map(int, input().split())
edges = [[] for _ in range(N)]
for i in range(1, N):
	edges[i].append((i - 1, 0))
for _ in range(M):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	edges[l].append((r, c))
que = [(0, 0)]
minDist = [float('inf')] * N
while que:
	(d, now) = heappop(que)
	if d >= minDist[now]:
		continue
	minDist[now] = d
	for (to, cost) in edges[now]:
		dist = d + cost
		if minDist[to] > dist:
			heappush(que, (dist, to))
ans = minDist[N - 1]
print(-1 if ans == float('inf') else ans)


(N, M) = map(int, input().split())
E = [[int(e) for e in input().split()] for _ in range(M)]
E.sort()
inf = 10 ** 15
seg = [inf] * (2 * N - 1)

def update(k, x):
	k += N - 1
	seg[k] = x
	while k:
		k = (k - 1) // 2
		seg[k] = min(seg[2 * k + 1], seg[2 * k + 2])

def query(p, q):
	p += N - 1
	q += N - 2
	res = inf
	while q - p > 1:
		if p & 1 == 0:
			res = min(res, seg[p])
		if q & 1 == 1:
			res = min(res, seg[q])
			q -= 1
		p //= 2
		q = (q - 1) // 2
	if p == q:
		res = min(res, seg[q])
	else:
		res = min(res, seg[p], seg[q])
	return res
update(0, 0)
for e in E:
	d = query(e[1] - 1, N)
	l = query(e[0] - 1, N)
	if l + e[2] < d:
		update(e[1] - 1, l + e[2])
if seg[-1] == inf:
	print(-1)
else:
	print(seg[-1])


(n, m) = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
	(a, b, cost) = list(map(int, input().split()))
	link[a - 1].append([b - 1, cost])
	link[b - 1].append([a - 1, cost])
for i in range(n - 1):
	link[i + 1].append([i, 0])
from heapq import heappush, heappop, heappushpop, heapify

def dks(g, start, num_v):
	INF = float('inf')
	visited = set()
	hq = []
	heappush(hq, (0, start))
	cost = [INF] * num_v
	while hq:
		(shortest, i) = heappop(hq)
		if i in visited:
			continue
		visited.add(i)
		cost[i] = shortest
		for (j, t) in g[i]:
			if j in visited:
				continue
			heappush(hq, (shortest + t, j))
	return cost
ans = dks(link, 0, n)
if ans[-1] != float('inf'):
	print(ans[-1])
else:
	print(-1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(m):
	(x, y, z) = map(int, input().split())
	edge[x - 1].append([z, y - 1])
	edge[y - 1].append([z, x - 1])
for i in range(1, n):
	edge[i].append([0, i - 1])
import heapq

def dijkstra_heap(s):
	d = [float('inf')] * n
	used = [True] * n
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, [e[0] + d[v], e[1]])
	return d
x = dijkstra_heap(0)[n - 1]
if x == float('inf'):
	print(-1)
else:
	print(x)


class SegTree:

	def __init__(self, N):
		self.N = N
		self._N = 1 << (N - 1).bit_length()
		self.node = [10 ** 15] * (2 * self._N - 1)
		self.node[self._N - 1] = 0

	def eval(self, p):
		i = p + self._N - 1
		cur = self.node[i]
		while i:
			i = (i - 1) // 2
			if cur > self.node[i]:
				cur = self.node[i]
		self.node[p + self._N - 1] = cur
		return cur

	def update(self, x, p, q, idx=0, a=0, b=None):
		if not idx:
			x += self.eval(p)
		if x >= 10 ** 15:
			return
		if b is None:
			b = self._N
		if q <= p or b <= p or q <= a:
			return
		elif p <= a and b <= q:
			if x < self.node[idx]:
				self.node[idx] = x
			return
		else:
			self.update(x, p, q, idx * 2 + 1, a, (a + b) // 2)
			self.update(x, p, q, idx * 2 + 2, (a + b) // 2, b)
			return
(n, m) = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
edge.sort()
tr = SegTree(n)
for (s, t, c) in edge:
	tr.update(c, s - 1, t)
ans = tr.eval(n - 1)
if ans >= 10 ** 15:
	ans = -1
print(ans)


class SegmentTree:

	def __init__(self, size, default, op=min):
		self.size = 2 ** size.bit_length()
		self.dat = [default] * (self.size * 2)
		self.op = op

	def update(self, i, x):
		i += self.size
		self.dat[i] = x
		while i > 0:
			i >>= 1
			self.dat[i] = self.op(self.dat[i * 2], self.dat[i * 2 + 1])

	def add(self, i, x):
		i += self.size
		self.dat[i] = self.op(self.dat[i], x)
		while i > 0:
			i >>= 1
			self.dat[i] = self.op(self.dat[i], x)

	def get(self, a, b=None):
		if b is None:
			b = a + 1
		(l, r) = (a + self.size, b + self.size)
		res = None
		while l < r:
			if l & 1:
				if res is None:
					res = self.dat[l]
				else:
					res = self.op(res, self.dat[l])
				l += 1
			if r & 1:
				r -= 1
				if res is None:
					res = self.dat[r]
				else:
					res = self.op(res, self.dat[r])
			l >>= 1
			r >>= 1
		return res
(N, M) = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
LRC.sort(key=lambda x: (x[0], x[1]))
INF = 10 ** 18
dp = SegmentTree(N, INF, min)
dp.update(0, 0)
for (l, r, c) in LRC:
	p = dp.get(l - 1, r - 1) + c
	if p < dp.get(r - 1):
		dp.update(r - 1, p)
print(dp.get(N - 1) if dp.get(N - 1) != INF else -1)


(n, m) = map(int, input().split())
inf = 10 ** 15
edges = [[] for _ in range(n)]
for _ in range(m):
	(l, r, c) = map(int, input().split())
	edges[l - 1].append((r - 1, c))
for i in range(n - 1):
	edges[i + 1].append((i, 0))
from heapq import heappop, heappush
d = [inf for _ in range(n)]

def dijkstra(s):
	que = []
	d[s] = 0
	heappush(que, (0, s))
	while len(que):
		(dist, node) = heappop(que)
		if d[node] < dist:
			continue
		for (to, cost) in edges[node]:
			if d[to] > dist + cost:
				d[to] = dist + cost
				heappush(que, (d[to], to))
dijkstra(0)
print(d[n - 1] if d[n - 1] != inf else -1)


from heapq import heappop, heappush
(N, M) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
edges = [[] for _ in range(N)]
for (u, v, c) in X:
	edges[u - 1].append((v - 1, c))
for i in range(N - 1):
	edges[i + 1].append((i, 0))
INF = float('inf')
d = [INF] * N
d[0] = 0
pq = []
heappush(pq, (0, 0))
while len(pq) > 0:
	(cost, u) = heappop(pq)
	for (v, c) in edges[u]:
		if d[v] > d[u] + c:
			d[v] = d[u] + c
			heappush(pq, (d[v], v))
print(d[-1] if d[-1] != INF else -1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
abd = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n + 1)]
for (a, b, d) in abd:
	graph[a].append((b, d))
for i in range(1, n):
	graph[i + 1].append((i, 0))
import heapq as hq
dist = [10 ** 18] * (n + 1)
dist[1] = 0
q = [(0, 1)]
hq.heapify(q)
while q:
	(d, x) = hq.heappop(q)
	for (y, dd) in graph[x]:
		if dist[y] > dist[x] + dd:
			dist[y] = dist[x] + dd
			hq.heappush(q, (dist[y], y))
if dist[n] == 10 ** 18:
	print(-1)
else:
	print(dist[n])


(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(l, r, c) = map(int, input().split())
	(l, r) = (l - 1, r - 1)
	G[l].append([r, c])
for i in range(1, N):
	G[i].append([i - 1, 0])

def dijkstra(graph, start, inf=float('inf')):
	import heapq
	n = len(graph)
	distances = [inf] * n
	distances[start] = 0
	visited = [False] * n
	hq = [(0, start)]
	while hq:
		(dist, fr) = heapq.heappop(hq)
		visited[fr] = True
		for (to, cost) in graph[fr]:
			new_dist = distances[fr] + cost
			if visited[to] or distances[to] <= new_dist:
				continue
			distances[to] = new_dist
			heapq.heappush(hq, (new_dist, to))
	return distances
ans = dijkstra(G, 0)[N - 1]
print(ans if ans != float('inf') else -1)


import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def main():
	to = defaultdict(list)
	(n, m) = map(int, input().split())
	for _ in range(m):
		(l, r, c) = map(int, input().split())
		(l, r) = (l - 1, r - 1)
		to[l].append([r, c])
	costs = [-1] * n
	hp = []
	heappush(hp, [0, 0])
	while hp:
		(c, u) = heappop(hp)
		if u == n - 1:
			print(c)
			exit()
		if costs[u] != -1:
			continue
		costs[u] = c
		for (v, dc) in to[u]:
			if costs[v] != -1:
				continue
			heappush(hp, [c + dc, v])
		for v in range(u - 1, 0, -1):
			if costs[v] != -1:
				break
			heappush(hp, [c, v])
	print(-1)
main()


import sys
import heapq
input = sys.stdin.readline
(heapify, push, pop) = (heapq.heapify, heapq.heappush, heapq.heappop)
(_n, _m) = map(int, input().split())
_lrc = []
for _ in range(_m):
	(l, r, c) = map(int, input().split())
	_lrc.append((l - 1, r - 1, c))
_lrc.sort()

def chker(n, m, lrc):
	dst = [float('inf')] * n
	dst[0] = 0
	q = [(0, 0)]
	cnt = 0
	for i in range(n):
		while q:
			(d, r) = q[0]
			if i <= r:
				break
			pop(q)
		else:
			print(-1)
			return
		dst[i] = d
		while cnt < m and lrc[cnt][0] == i:
			(l, r, c) = lrc[cnt]
			push(q, (d + c, r))
			cnt += 1
	print(dst[-1])
chker(_n, _m, _lrc)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
t = sorted([tuple(map(int, input().split())) for i in range(m)])
d = [0, 0] + [1e+18] * n
for (l, r, c) in t:
	for i in range(r, l, -1):
		if d[l] + c < d[i]:
			d[i] = d[l] + c
		else:
			break
print(d[-2] % 10 ** 18 or -1)


(n, m) = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
edge.sort()
from heapq import heappop, heapify, heappush
heapify(edge)
heap = [(0, 1)]
dist = [float('inf')] * (n + 1)
while heap:
	(cost, cur) = heappop(heap)
	if dist[cur] <= cost:
		continue
	dist[cur] = cost
	while edge:
		if edge[0][0] <= cur:
			(l, r, c) = heappop(edge)
			if r < cur:
				continue
			heappush(heap, (cost + c, r))
		else:
			break
if dist[-1] == float('inf'):
	print(-1)
else:
	print(dist[-1])


import sys
import bisect
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
LRC = [list(map(int, input().split())) for i in range(M)]
LRC.sort()
INF = 100100100100100100
dist = [INF] * N
dist[0] = 0
for (li, ri, ci) in LRC:
	td = dist[li - 1] + ci
	ti = bisect.bisect(dist, dist[li - 1] + ci)
	ti = min(ti, ri + 1)
	for i in range(ti, ri):
		dist[i] = td
ans = dist[-1]
if ans == INF:
	ans = -1
print(ans)


from heapq import heappush, heappop
(N, M) = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(1, N):
	graph[i].append((i - 1, 0))
for i in range(M):
	(l, r, c) = map(int, input().split())
	graph[l - 1].append((r - 1, c))
dist = [-1] * N
d = [(0, 0)]
while d:
	(cost, node) = heappop(d)
	if dist[node] >= 0:
		continue
	dist[node] = cost
	for (child, c) in graph[node]:
		if dist[child] >= 0:
			continue
		heappush(d, (cost + c, child))
print(dist[-1])


INF = 10 ** 15
MOD = 10 ** 9 + 7
from heapq import heappop, heappush, heapify

def dijkstra(G, start=0):
	N = len(G)
	dist = [INF] * N
	dist[start] = 0
	q = [(0, start)]
	while q:
		(d, v) = heappop(q)
		if d > dist[v]:
			continue
		for (e, c) in G[v]:
			if dist[v] + c < dist[e]:
				dist[e] = dist[v] + c
				heappush(q, (dist[e], e))
	return dist[-1]

def main():
	(N, M) = map(int, input().split())
	G = [[] for _ in range(N)]
	for _ in range(M):
		(l, r, c) = map(int, input().split())
		l -= 1
		r -= 1
		G[l].append((r, c))
		G[r].append((l, c))
	for i in range(N - 1):
		G[i + 1].append((i, 0))
	ans = dijkstra(G)
	print(ans if ans < INF else -1)
main()


import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline
inf = 10 ** 18

def dijkstra(repn, start, goal):
	dist = [inf for i in range(N + 1)]
	dist[start] = 0
	q = []
	heapq.heappush(q, (0, start))
	while q:
		(prov_cost, src) = heapq.heappop(q)
		if dist[src] < prov_cost:
			continue
		for dest in repn[src]:
			cost = repn[src][dest]
			if dist[dest] > dist[src] + cost:
				dist[dest] = dist[src] + cost
				heapq.heappush(q, (dist[dest], dest))
	return dist[goal]
(N, M) = map(int, input().split())
repn = [defaultdict(list) for _ in range(N + 1)]
for i in range(2, N + 1):
	repn[i][i - 1] = 0
for _ in range(M):
	(l, r, c) = map(int, input().split())
	if repn[l][r] == [] or repn[l][r] > c:
		repn[l][r] = c
d = dijkstra(repn, 1, N)
if d == inf:
	print(-1)
else:
	print(d)


from heapq import heappush, heappop
INF = 10 ** 15
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	graph[l].append((r, c))
for i in range(n - 1):
	graph[i + 1].append((i, 0))

def dijkstra(N, G, s):
	global dist
	dist = [INF] * N
	que = [(0, s)]
	dist[s] = 0
	while que:
		(c, v) = heappop(que)
		if dist[v] < c:
			continue
		for (t, cost) in G[v]:
			if dist[v] + cost < dist[t]:
				dist[t] = dist[v] + cost
				heappush(que, (dist[t], t))
dijkstra(n, graph, 0)
if dist[n - 1] == INF:
	print(-1)
else:
	print(dist[n - 1])


import sys
from heapq import heappop, heappush, heapify

def dijkstra(s, t, links):
	heap = list(links[s])
	heapify(heap)
	visited = set()
	while len(heap) > 0:
		(cost, node) = heappop(heap)
		if node == t:
			return cost
		if node in visited:
			continue
		visited.add(node)
		for (cost2, node2) in links[node]:
			if node2 in visited:
				continue
			heappush(heap, (cost + cost2, node2))
	return -1

def main():
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	links = [[] for _ in range(N)]
	for i in range(1, N):
		links[i].append((0, i - 1))
	for _ in range(M):
		(l, r, c) = map(int, input().split())
		links[l - 1].append((c, r - 1))
	return dijkstra(0, N - 1, links)
print(main())


import heapq
import sys
input = sys.stdin.readline

def dijkstra(s, edge):
	d = [float('inf')] * n
	used = [True] * n
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, [e[0] + d[v], e[1]])
	return d
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for i in range(n - 1):
	edge[i + 1].append([0, i])
for _ in range(m):
	(u, v, w) = map(int, input().split())
	edge[u - 1].append([w, v - 1])
	edge[v - 1].append([w, u - 1])
d = dijkstra(0, edge)
if d[n - 1] == float('inf'):
	print(-1)
else:
	print(d[n - 1])


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())

def init_min(init_min_val):
	for i in range(n):
		seg_min[i + num_max - 1] = init_min_val[i]
	for i in range(num_max - 2, -1, -1):
		seg_min[i] = min(seg_min[2 * i + 1], seg_min[2 * i + 2])

def update_min(k, x):
	k += num_max - 1
	seg_min[k] = x
	while k:
		k = (k - 1) // 2
		seg_min[k] = min(seg_min[k * 2 + 1], seg_min[k * 2 + 2])

def query_min(p, q):
	if q <= p:
		return ide_ele_min
	p += num_max - 1
	q += num_max - 2
	res = ide_ele_min
	while q - p > 1:
		if p & 1 == 0:
			res = min(res, seg_min[p])
		if q & 1 == 1:
			res = min(res, seg_min[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = min(res, seg_min[p])
	else:
		res = min(min(res, seg_min[p]), seg_min[q])
	return res
ide_ele_min = 10 ** 20
num_max = 2 ** (len(str(bin(n - 1))) - 2)
seg_min = [ide_ele_min] * 2 * num_max
update_min(0, 0)
rlc = []
for i in range(m):
	(l, r, c) = map(int, input().split())
	rlc.append((r, l, c))
rlc.sort()
for tmp in rlc:
	(r, l, c) = tmp
	l = l - 1
	r = r - 1
	update_min(r, min(query_min(l, r) + c, query_min(r, r + 1)))
ans = query_min(n - 1, n)
if ans == ide_ele_min:
	print(-1)
else:
	print(ans)


def func(x, y):
	return min(x, y)

class SegmentTree:

	def __init__(self, n):
		n_ = 1
		while n_ < n:
			n_ *= 2
		self.n = n_
		self.arr = [10 ** 18] * (2 * self.n - 1)

	def update(self, k, a):
		k += self.n - 1
		self.arr[k] = a
		while k > 0:
			k = (k - 1) // 2
			self.arr[k] = min(self.arr[2 * k + 1], self.arr[2 * k + 2])

	def query(self, l, r):
		(L, R) = (l + self.n, r + self.n)
		ide_ele = float('inf')
		res = ide_ele
		while L < R:
			if R & 1:
				R -= 1
				res = func(res, self.arr[R - 1])
			if L & 1:
				res = func(res, self.arr[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return res
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
lrc = [tuple(map(int, input().split())) for _ in range(m)]
dp = SegmentTree(n + 1)
dp.update(1, 0)
rl = [[] for _ in range(n + 1)]
rc = [[] for _ in range(n + 1)]
for (l, r, c) in lrc:
	rl[r].append(l)
	rc[r].append(c)
for r in range(2, n + 1):
	x = float('inf')
	for (l, c) in zip(rl[r], rc[r]):
		y = dp.query(l, r) + c
		if x > y:
			x = y
	dp.update(r, x)
	if r == n:
		ans = x
if ans == float('inf'):
	ans = -1
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from heapq import heappop, heappush

def main():
	(n, m) = map(int, input().split())
	edges = [[] for _ in range(n)]
	for i in range(1, n):
		edges[i] = [(i - 1, 0)]
	lrc = [tuple(map(int, input().split())) for _ in range(m)]
	for (l, r, c) in lrc:
		edges[l - 1].append((r - 1, c))
	d = [float('inf') for _ in range(n)]
	d[0] = 0
	h = [(0, 0)]
	while len(h) > 0:
		(tmpd, tmpi) = heappop(h)
		for (toi, tod) in edges[tmpi]:
			if d[toi] > tmpd + tod:
				d[toi] = tmpd + tod
				heappush(h, (d[toi], toi))
	if d[n - 1] == float('inf'):
		print(-1)
	else:
		print(d[n - 1])
main()


import sys
input = sys.stdin.buffer.readline
INF = float('inf')
from collections import defaultdict
from heapq import heappop, heappush

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

class Graph(object):

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

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

	def add_edge(self, a, b, w):
		self.graph[a].append((b, w))

	def get_nodes(self):
		return self.graph.keys()

class Dijkstra(object):

	def __init__(self, graph, s):
		self.g = graph.graph
		self.dist = defaultdict(lambda : INF)
		self.dist[s] = 0
		self.prev = defaultdict(lambda : None)
		self.Q = []
		heappush(self.Q, (self.dist[s], s))
		while self.Q:
			(dist_u, u) = heappop(self.Q)
			if self.dist[u] < dist_u:
				continue
			for (v, w) in self.g[u]:
				alt = dist_u + w
				if self.dist[v] > alt:
					self.dist[v] = alt
					self.prev[v] = u
					heappush(self.Q, (alt, v))

def main():
	(N, M) = getlist()
	G = Graph()
	for i in range(M):
		(L, R, C) = getlist()
		G.add_edge(L - 1, R - 1, C)
	for i in range(N - 1):
		G.add_edge(i + 1, i, 0)
	D = Dijkstra(G, 0)
	if D.dist[N - 1] == INF:
		print(-1)
	else:
		print(D.dist[N - 1])
main()


import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(1, N):
	G[i].append([i - 1, 0])
for i in range(M):
	(L, R, C) = map(int, input().split())
	G[L - 1].append([R - 1, C])
S = 0

def dijkstra(N, S):
	d = [INF for i in range(N)]
	que = []
	d[S] = 0
	heapq.heappush(que, [0, S])
	while not len(que) == 0:
		q = heapq.heappop(que)
		ver = q[1]
		dis = q[0]
		if d[ver] < dis:
			continue
		for i in range(len(G[ver])):
			e = G[ver][i]
			if d[e[0]] > d[ver] + e[1]:
				d[e[0]] = d[ver] + e[1]
				heapq.heappush(que, [d[e[0]], e[0]])
	return d[N - 1]
ans = dijkstra(N, S)
if ans == INF:
	print(-1)
else:
	print(ans)


from heapq import heappop, heappush, heapify
import sys
input = lambda : sys.stdin.readline().rstrip()
inpl = lambda : list(map(int, input().split()))
(N, M) = inpl()
LRC = sorted([(lambda L, R, C: (L - 1, R - 1, C))(*inpl()) for _ in range(M)])
m = 0
dq = [(0, 0)]
for i in range(N):
	while dq and dq[0][1] < i:
		heappop(dq)
	if not dq:
		print(-1)
		break
	d = dq[0][0]
	while m < M and LRC[m][0] == i:
		heappush(dq, (d + LRC[m][2], LRC[m][1]))
		m += 1
else:
	print(d)


import sys
from heapq import heappop, heappush
from collections import defaultdict
input = sys.stdin.buffer.readline
INF = 10 ** 20
(N, M) = map(int, input().split())
g = defaultdict(list)
for i in range(2, N + 1):
	g[i].append((i - 1, 0))
for i in range(1, M + 1):
	(l, r, c) = list(map(int, input().split()))
	g[l].append((r, c))
d = [INF] * (N + 1)
d[1] = 0
que = []
heappush(que, (1, 0))
while que:
	(s, dist) = heappop(que)
	if d[s] < dist:
		continue
	for (t, c) in g[s]:
		if d[t] > d[s] + c:
			d[t] = d[s] + c
			heappush(que, (t, d[t]))
if d[N] == INF:
	print(-1)
	exit()
print(d[N])


import sys
input = sys.stdin.readline
import heapq

def main():
	(N, M) = map(int, input().split())
	d = dict()
	E = [[] for _ in range(N)]
	for i in range(N - 1):
		E[i + 1].append((0, i))
	for _ in range(M):
		(l, r, c) = map(int, input().split())
		l -= 1
		r -= 1
		E[l].append((c, r))
	q = [(0, 0)]
	heapq.heapify(q)
	path = [-1] * N
	while q:
		(c, v) = heapq.heappop(q)
		if path[v] >= 0:
			continue
		path[v] = c
		for (cost, e) in E[v]:
			if path[e] == -1:
				heapq.heappush(q, (c + cost, e))
	print(path[-1])
main()


from heapq import heappop, heappush
(N, M) = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = float('inf')

def dijkstra(s, n, g):
	que = []
	d = [INF for _ in range(n)]
	d[s] = 0
	heappush(que, (0, s))
	while len(que) > 0:
		p = heappop(que)
		v = p[1]
		if d[v] < p[0]:
			continue
		for i in range(len(g[v])):
			edge = g[v][i]
			if d[edge[0]] > d[v] + edge[1]:
				d[edge[0]] = d[v] + edge[1]
				heappush(que, (d[edge[0]], edge[0]))
	return d
G = [[] for _ in range(N)]
for i in range(N - 1):
	G[i + 1].append((i, 0))
for (l, r, c) in LRC:
	l -= 1
	r -= 1
	G[l].append((r, c))
p = dijkstra(0, N, G)[N - 1]
print(p if p != INF else -1)


import heapq
(N, M) = map(int, input().split())
edge_list = [[] for i in range(N + 1)]
for i in range(2, N + 1):
	edge_list[i].append((0, i - 1))
for i in range(M):
	(L, R, C) = map(int, input().split())
	edge_list[L].append((C, R))

def solve(s, t):
	fixed = {}
	q = []
	heapq.heappush(q, (0, s))
	while q:
		(w, x) = heapq.heappop(q)
		if x == t:
			return w
		if x in fixed:
			continue
		fixed[x] = w
		for (c, y) in edge_list[x]:
			if y not in fixed:
				heapq.heappush(q, (w + c, y))
	return None
answer = solve(1, N)
if answer is None:
	print(-1)
else:
	print(answer)


import sys
input = sys.stdin.readline
import heapq
(N, M) = map(int, input().split())
LRC = [tuple(map(int, input().split())) for i in range(M)]
es = [[] for i in range(N)]
for (l, r, c) in LRC:
	(l, r) = (l - 1, r - 1)
	es[l].append((r, c))
for i in range(N - 1):
	es[i + 1].append((i, 0))
INF = 10 ** 18
dist = [INF] * N
dist[0] = 0
hq = [(0, 0)]
heapq.heapify(hq)
while hq:
	(d, v) = heapq.heappop(hq)
	if v == N - 1:
		print(d)
		exit()
	for (to, c) in es[v]:
		if d + c >= dist[to]:
			continue
		dist[to] = d + c
		heapq.heappush(hq, (d + c, to))
print(-1)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
B = [tuple(map(int, input().split())) for i in range(M)]
B.sort()
seg_el = 1 << (N + 1).bit_length()
SEG = [1 << 60] * (2 * seg_el)
SEG[1 + seg_el] = 0

def getvalue(n, seg_el):
	i = n + seg_el
	ANS = 1 << 60
	ANS = min(SEG[i], ANS)
	i >>= 1
	while i != 0:
		ANS = min(SEG[i], ANS)
		i >>= 1
	return ANS

def updates(l, r, x):
	L = l + seg_el
	R = r + seg_el
	while L < R:
		if L & 1:
			SEG[L] = min(x, SEG[L])
			L += 1
		if R & 1:
			R -= 1
			SEG[R] = min(x, SEG[R])
		L >>= 1
		R >>= 1
for (l, r, c) in B:
	x = getvalue(l, seg_el)
	updates(l, r + 1, x + c)
if getvalue(N, seg_el) == 1 << 60:
	print(-1)
else:
	print(getvalue(N, seg_el))


import sys
read = sys.stdin.readline

class segtree:

	def __init__(self, n, op, e):
		self.e = e
		self.op = op
		self.size = 1 << (n - 1).bit_length()
		self.SEG = [self.e] * (self.size * 2)

	def update(self, i, x):
		i += self.size
		self.SEG[i] = x
		while i > 0:
			i >>= 1
			self.SEG[i] = self.op(self.SEG[i * 2], self.SEG[i * 2 + 1])

	def get(self, i):
		return self.SEG[i + self.size]

	def query(self, l, r):
		l += self.size
		r += self.size
		(lres, rres) = (self.e, self.e)
		while l < r:
			if l & 1:
				lres = self.op(lres, self.SEG[l])
				l += 1
			if r & 1:
				r -= 1
				rres = self.op(rres, self.SEG[r])
			l >>= 1
			r >>= 1
		res = self.op(lres, rres)
		return res
INF = float('inf')
(N, M) = map(int, read().split())
Q = []
for i in range(M):
	(l, r, c) = map(int, read().split())
	Q.append((l - 1, r - 1, c))
Q.sort(key=lambda x: x[0])
seg = segtree(N, min, INF)
seg.update(0, 0)
for (L, R, C) in Q:
	res = seg.query(L, R) + C
	if seg.get(R) > res:
		seg.update(R, res)
ans = seg.get(N - 1)
print(ans if ans != INF else -1)


from heapq import heappush, heappop
(n, m) = map(int, input().split())
a = [[[i - 1, 0]] for i in range(n + 1)]
a[0] = []
for i in range(m):
	(l, r, c) = map(int, input().split())
	a[l].append([r, c])
q = [float('INF')] * (n + 1)
q[1] = 0
c = []
heappush(c, [0, 1])
while c:
	(s, t) = heappop(c)
	if t == n:
		print(s)
		break
	for (i, j) in a[t]:
		if q[i] > s + j:
			q[i] = s + j
			heappush(c, [s + j, i])
else:
	print(-1)


import heapq
(n, m) = map(int, input().split())
edge = [[]] + [[(0, i)] for i in range(n - 1)]
for _ in range(m):
	(l, r, c) = map(int, input().split())
	edge[l - 1].append((c, r - 1))
inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue and (not check[-1]):
	(dist, act) = heapq.heappop(queue)
	check[act] = True
	for (cost, vertex) in edge[act]:
		if check[vertex]:
			continue
		d = dist + cost
		if dp[vertex] > d:
			heapq.heappush(queue, (d, vertex))
			dp[vertex] = d
if dp[-1] < inf:
	print(dp[-1])
else:
	print(-1)


(n, m, *t) = map(int, open(0).read().split())
d = [0, 0] + [1e+18] * n
for (l, r, c) in sorted(zip(*[iter(t)] * 3)):
	for i in range(r, l, -1):
		if d[l] + c < d[i]:
			d[i] = d[l] + c
		else:
			break
print(d[-2] % 10 ** 18 or -1)


import math
import queue
import bisect
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	(n, m) = map(int, ipt().split())
	way = [[] for i in range(n + 1)]
	for _ in range(m):
		(l, r, c) = map(int, ipt().split())
		way[l].append((r, c))
	for i in range(1, n):
		way[i + 1].append((i, 0))
	hq = [(0, 1)]
	dst = [10 ** 18] * (n + 1)
	dst[1] = 0
	while hq:
		(di, qi) = hpq.heappop(hq)
		for (j, cj) in way[qi]:
			if dst[j] > di + cj:
				dst[j] = di + cj
				hpq.heappush(hq, (di + cj, j))
	print((dst[n] + 1) % (10 ** 18 + 1) - 1)
	return None
main()


(N, M) = map(int, input().split(' '))
tree_list = [[] for _ in range(N)]
LRC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: (x[0], x[1]))
inf = float('inf')
dp = [inf] * N
dp[0] = 0
flag = False
if LRC[0][0] != 1:
	print(-1)
else:
	for (l, r, c) in LRC:
		l = l - 1
		r = r - 1
		if dp[r] > dp[l] + c:
			for i in reversed(range(l + 1, r + 1)):
				if dp[i] > dp[l] + c:
					dp[i] = dp[l] + c
				else:
					break
	if dp[N - 1] < inf:
		print(dp[N - 1])
	else:
		print(-1)


from sys import stdin
import heapq
(N, M) = [int(x) for x in stdin.readline().rstrip().split()]
B = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
graph = [[] for _ in range(N)]
for i in range(1, N):
	graph[i].append((0, i - 1))
for m in B:
	graph[m[0] - 1].append((m[2], m[1] - 1))
d = [(0, 0)]
distance = [10 ** 15] * N
distance[0] = 0
color = ['white'] * N
heapq.heapify(d)
while len(d) > 0:
	(temp, u) = heapq.heappop(d)
	color[u] = 'black'
	if distance[u] < temp:
		continue
	for v in graph[u]:
		if color[v[1]] != 'black':
			if distance[u] + v[0] < distance[v[1]]:
				distance[v[1]] = distance[u] + v[0]
				color[v[1]] = 'gray'
				heapq.heappush(d, (distance[v[1]], v[1]))
if distance[N - 1] == 10 ** 15:
	print(-1)
else:
	print(distance[N - 1])


from heapq import heappop, heappush, heapify
import sys
sys.setrecursionlimit(10 ** 9)
input = lambda : sys.stdin.readline().rstrip()
inpl = lambda : list(map(int, input().split()))
(N, M) = inpl()
q = []
LRC = sorted([inpl() for _ in range(M)])
points = sorted(list({lrc[i] for i in range(2) for lrc in LRC}))
if points[0] != 1 or points[-1] != N:
	print(-1)
	exit()
positions = dict()
P = 0
prev = -1
for p in points:
	if p > prev:
		prev = p
		positions[p] = P
		P += 1
m = 0
dq = [(0, 0)]
for i in range(P):
	while dq and dq[0][1] < i:
		heappop(dq)
	if not dq:
		print(-1)
		break
	d = dq[0][0]
	while m < M and positions[LRC[m][0]] == i:
		heappush(dq, (d + LRC[m][2], positions[LRC[m][1]]))
		m += 1
else:
	print(d)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
C = [list(map(int, input().split())) for i in range(m)]
S = [0] * n
for i in range(m):
	for j in range(2):
		C[i][j] -= 1
for i in range(m):
	S[C[i][0]] += 1
	S[C[i][1]] -= 1
for i in range(1, n):
	S[i] += S[i - 1]
for i in range(n - 1):
	if S[i] > 0:
		C.append([i + 1, i, 0])
M = [[] for i in range(n)]
for i in range(len(C)):
	M[C[i][0]].append([C[i][1], C[i][2]])
	if C[i][2] > 0:
		M[C[i][1]].append([C[i][0], C[i][2]])
import heapq
D = [float('inf')] * n
P = [-1] * n
D[0] = 0
V = [0] * n
Q = []
for v in range(n):
	heapq.heappush(Q, [D[v], v])
le = len(Q)
while le > 0:
	q = heapq.heappop(Q)
	u = q[1]
	du = q[0]
	if V[u] == 0:
		V[u] = 1
		le -= 1
		for i in range(len(M[u])):
			v = M[u][i][0]
			luv = M[u][i][1]
			if V[v] == 0:
				alt = du + luv
				if D[v] > alt:
					D[v] = alt
					P[v] = u
					heapq.heappush(Q, [alt, v])
ans = D[-1]
if ans == float('inf'):
	ans = -1
print(ans)


from heapq import *
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N - 1):
	G[i + 1].append((i, 0))
(l, r, c) = (0, 0, 0)
for i in range(M):
	(l, r, c) = map(int, input().split())
	G[l - 1].append((r - 1, c))
D = [0] * N
INF = 10 ** 20

def ijk(s):
	global D, INF, G
	for i in range(len(G)):
		D[i] = INF
	D[s] = 0
	Q = []
	heapify(Q)
	heappush(Q, (0, s))
	(p, v, e) = (0, 0, 0)
	while len(Q):
		p = heappop(Q)
		v = p[1]
		if D[v] < p[0]:
			continue
		for i in range(len(G[v])):
			e = G[v][i]
			if D[e[0]] > D[v] + e[1]:
				D[e[0]] = D[v] + e[1]
				heappush(Q, (D[e[0]], e[0]))
ijk(0)
if D[-1] >= INF:
	print(-1)
else:
	print(D[-1])


class SegmentTree:

	def __init__(self, n, INF):
		self.n = n
		self.INF = INF
		self.log = (n - 1).bit_length()
		self.size = 1 << self.log
		self.data = [self.INF] * (2 * self.size)

	def get(self, p):
		res = self.INF
		p += self.size
		for _ in range(self.log + 1):
			res = min(res, self.data[p])
			p >>= 1
		return res

	def set(self, p, x):
		p += self.size
		self.data[p] = x

	def range_set(self, l, r, x):
		l += self.size
		r += self.size
		while l < r:
			if l & 1:
				self.data[l] = min(self.data[l], x)
				l += 1
			if r & 1:
				r -= 1
				self.data[r] = min(self.data[r], x)
			l >>= 1
			r >>= 1
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
INF = 10 ** 18
lst = SegmentTree(N, INF)
lst.set(0, 0)
A = [list(map(int, input().split())) for _ in range(M)]
A.sort(key=lambda x: (x[0], x[1]))
for (l, r, c) in A:
	lst.range_set(l - 1, r, lst.get(l - 1) + c)
ans = lst.get(N - 1)
print(ans if ans < INF else -1)


def getN():
	return int(input())

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

def getList():
	return list(map(int, input().split()))
import heapq
INF = 10 ** 11

def main():
	(n, m) = getList()
	begin = [[] for i in range(n)]
	cost = [-1 for i in range(n)]
	for i in range(m):
		(st, en, cos) = getList()
		begin[st - 1].append((cos, en - 1))
	h = []
	for warp in begin[0]:
		heapq.heappush(h, warp)
	cur_mas = 0
	while h:
		cand = heapq.heappop(h)
		if cand[1] > cur_mas:
			cur_mas += 1
			cost[cur_mas] = cand[0]
			for warp in begin[cur_mas]:
				(tcos, ten) = (warp[0] + cost[cur_mas], warp[1])
				heapq.heappush(h, (tcos, ten))
			heapq.heappush(h, cand)
	print(cost[n - 1])
main()


INF = 10 ** 14

class BIT:

	def __init__(self, max):
		self.max = max
		self.data = [INF] * (self.max + 1)

	def update(self, i, x):
		while i > 0:
			self.data[i] = min(self.data[i], x)
			i -= i & -i

	def read(self, i):
		m = INF
		while i <= self.max:
			m = min(self.data[i], m)
			i += i & -i
		return m
import sys
input = sys.stdin.readline
from operator import itemgetter
(N, M) = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
LRC.sort(key=itemgetter(0))
bit = BIT(N)
bit.update(1, 0)
for (l, r, c) in LRC:
	m = bit.read(l)
	bit.update(r, m + c)
ans = bit.data[N]
if ans == INF:
	print(-1)
else:
	print(ans)


import sys
(n, m) = list(map(int, input().split()))
pl = []
for _ in range(m):
	(l, r, c) = list(map(int, input().split()))
	pl.append((l - 1, r - 1, c))
dp = [float('inf') for i in range(n)]
dp[0] = 0
pl = sorted(pl)
for (l, r, c) in pl:
	for rr in range(r, l, -1):
		if dp[rr] > dp[l] + c:
			dp[rr] = dp[l] + c
		else:
			break
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


import sys
import heapq
sys.setrecursionlimit(10 ** 7)
(n, m) = [int(i) for i in sys.stdin.readline().split()]
INF = 10 ** 9
graph = {j: [(j - 1, 1e-10)] if j > 0 else [] for j in range(n)}
for i in range(m):
	(l, r, c) = [int(i) for i in sys.stdin.readline().split()]
	l -= 1
	r -= 1
	graph[l].append((r, c))
	graph[r].append((l, c))
que = [(0, 0)]
already = set()
res = [-1 for i in range(n)]
while len(que) > 0:
	(cost, cand) = heapq.heappop(que)
	if cand in already:
		continue
	res[cand] = cost
	already.add(cand)
	for (_next, _next_cost) in graph[cand]:
		if _next in already:
			continue
		heapq.heappush(que, (cost + _next_cost, _next))
print(int(res[-1]))


from heapq import heappush, heappop
from collections import defaultdict
INF = float('inf')

def dijkstra(V, E, s):
	dist = {v: INF for v in V}
	heap = []
	dist[s] = 0
	rem = len(V)
	heappush(heap, (0, s))
	while heap and rem:
		(d, v) = heappop(heap)
		if d > dist[v]:
			continue
		rem -= 1
		for (u, c) in E[v].items():
			temp = d + c
			if temp < dist[u]:
				dist[u] = temp
				heappush(heap, (temp, u))
	return dist
(N, M) = map(int, input().split())
V = list(range(N))
E = defaultdict(dict)
for i in range(N):
	E[i + 1][i] = 0
for _ in range(M):
	(l, r, c) = map(int, input().split())
	(l, r) = (l - 1, r - 1)
	E[l][r] = min(c, E[l].setdefault(r, INF))
dist = dijkstra(V, E, 0)
print(dist[N - 1] if dist[N - 1] != INF else -1)


def main():
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(m)]
	a.sort()
	INF = 10 ** 18
	dp = [INF for i in range(n)]
	dp[0] = 0
	for (l, r, c) in a:
		if dp[l - 1] == INF:
			print(-1)
			return None
		tp = dp[l - 1] + c
		for i in range(r - 1, l - 1, -1):
			if dp[i] == INF:
				dp[i] = tp
			elif tp < dp[i]:
				dp[i] = tp
			else:
				break
	if dp[-1] == INF:
		print(-1)
	else:
		print(dp[-1])
main()


from heapq import heappop, heappush, heapify
import sys
input = lambda : sys.stdin.readline().rstrip()
inpl = lambda : list(map(int, input().split()))
(N, M) = inpl()
LRC = sorted([inpl() for _ in range(M)])
points = sorted(list({lrc[i] for i in range(2) for lrc in LRC}))
if points[0] > 1 or points[-1] < N:
	print(-1)
	exit()
dq = [(0, 1)]
m = 0
for i in points:
	while dq and dq[0][1] < i:
		heappop(dq)
	if not dq:
		print(-1)
		break
	d = dq[0][0]
	while m < M and LRC[m][0] == i:
		heappush(dq, (d + LRC[m][2], LRC[m][1]))
		m += 1
else:
	print(d)


import heapq
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(1, n):
	(_from, to, dist) = (i, i - 1, 0)
	edges[_from].append([to, dist])
for _ in range(m):
	(_from, to, dist) = map(int, input().split())
	edges[_from - 1].append([to - 1, dist])
D = [float('INF')] * n
D[0] = 0
todo = []
for (to, dist) in edges[0]:
	heapq.heappush(todo, [dist, to])
	D[to] = dist
while todo:
	(total_dist, node) = heapq.heappop(todo)
	for (to, dist) in edges[node]:
		if total_dist + dist < D[to]:
			heapq.heappush(todo, [total_dist + dist, to])
			D[to] = total_dist + dist
		else:
			continue
ans = D[n - 1]
if ans == float('INF'):
	ans = -1
print(ans)


import heapq
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for i in range(n - 1):
	edge[i + 1].append([0, i])
for _ in range(m):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	edge[l].append([c, r])
	edge[r].append([c, l])

def dijkstra_heap(s):
	infi = 10 ** 18
	d = [infi] * n
	used = [True] * n
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, [e[0] + d[v], e[1]])
	if d[n - 1] != infi:
		return d[n - 1]
	else:
		return -1
print(dijkstra_heap(0))


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

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

def li_():
	return map(lambda x: int(x) - 1, stdin.readline().split())

def lf():
	return map(float, stdin.readline().split())

def ls():
	return stdin.readline().split()

def ns():
	return stdin.readline().rstrip()

def lc():
	return list(ns())

def ni():
	return int(stdin.readline())

def nf():
	return float(stdin.readline())
from bisect import bisect_right
(n, m) = li()
lrc = [list(li()) for _ in range(m)]
lrc = sorted(lrc, key=lambda x: x[2])
lrc = sorted(lrc, key=lambda x: x[1])
lrc = sorted(lrc, key=lambda x: x[0])
INF = float('inf')
dist = [INF] * n
dist[0] = 0
for (left_idx, right_idx, ci) in lrc:
	left_idx -= 1
	newleft_idx = bisect_right(dist, dist[left_idx] + ci)
	for idx in range(newleft_idx, right_idx):
		dist[idx] = dist[left_idx] + ci
if dist[-1] == INF:
	print(-1)
else:
	print(dist[-1])


from heapq import *
(n, _, *t) = map(int, open(0).read().split())
e = [[] for _ in '_' * n]
for (l, r, c) in zip(*[iter(t)] * 3):
	e[l - 1] += ((c, r - 1),)
for i in range(n - 1):
	e[i + 1] += ((0, i),)
d = [0] + [1e+18] * n
q = [(0, 0)]
while q:
	(c, v) = heappop(q)
	for (b, w) in e[v]:
		if b + c < d[w]:
			d[w] = b + c
			heappush(q, (b + c, w))
print(-(d[-2] > 1e+17) or d[-2])


import sys

class SegTreeMin:

	def __init__(self, n, max_v):
		self.n = n
		n2 = 1
		while n2 < n:
			n2 <<= 1
		self.n2 = n2
		self.tree = [max_v] * (n2 << 1)
		self.INF = max_v

	def update(self, i, x):
		i += self.n2
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
			i >>= 1

	def get_min(self, a, b):
		result = self.INF
		q = [(1, 0, self.n2)]
		while q:
			(k, l, r) = q.pop()
			if a <= l and r <= b:
				result = min(result, self.tree[k])
				continue
			m = (l + r) // 2
			k <<= 1
			if a < m and l < b:
				q.append((k, l, m))
			if a < r and l < m:
				q.append((k + 1, m, r))
		return result

def solve():
	input = sys.stdin.readline
	mod = 10 ** 9 + 7
	(n, m) = list(map(int, input().rstrip('\n').split()))
	seg_tree = SegTreeMin(n, 10 ** 15)
	seg_tree.update(0, 0)
	lrc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
	lrc.sort()
	for (l, r, c) in lrc:
		l -= 1
		r -= 1
		tm = seg_tree.get_min(l, r)
		seg_tree.update(r, min(tm + c, seg_tree.get_min(r, r + 1)))
	mt = seg_tree.get_min(n - 1, n)
	print(mt if mt != 10 ** 15 else -1)
solve()


(N, M) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
INF = float('inf')
dp = [INF] * (N + 1)
dp[1] = 0
for (l, r, c) in sorted(X):
	for i in range(r, l, -1):
		if dp[i] > dp[l] + c:
			dp[i] = dp[l] + c
		else:
			break
print(dp[-1] if dp[-1] < INF else -1)


import heapq
import sys

class rode:

	def __init__(self, x, y):
		self.x = x
		self.y = y

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

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

	def __le__(self, other):
		return not other > self

	def __ge__(self, other):
		return not self > other
(n, m) = map(int, input().split())
da = [[] for i in range(n)]
for i in range(m):
	(l, r, c) = map(int, input().split())
	da[l - 1].append([r - 1, c])
for i in range(1, n):
	da[i].append([i - 1, 0])
pq = []
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
	heapq.heappush(pq, rode(i[0], i[1]))
while len(pq):
	now = heapq.heappop(pq)
	if now.x == n - 1:
		print(now.y)
		sys.exit()
	if ju[now.x]:
		continue
	ju[now.x] = True
	for i in da[now.x]:
		if ju[i[0]]:
			continue
		heapq.heappush(pq, rode(i[0], now.y + i[1]))
print(-1)


import heapq
(N, M) = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
	(l, r, c) = map(int, input().split())
	path[l - 1].append([r, c])
for i in range(1, N):
	path[i].append([i, 0])
dist = [float('inf')] * N
dist[0] = 0
q = [[dist[i], i] for i in range(N)]
heapq.heapify(q)
while q:
	(d, ind) = heapq.heappop(q)
	if d <= dist[ind]:
		for i in range(len(path[ind])):
			(r, c) = path[ind][i]
			if dist[r - 1] > d + c:
				dist[r - 1] = d + c
				heapq.heappush(q, [dist[r - 1], r - 1])
if dist[N - 1] == float('inf'):
	print(-1)
else:
	print(dist[N - 1])


from sys import stdout
import heapq
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
DBG = True and False
BIG = 999999999
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)

def dumpheap(h):
	a = []
	print('- -')
	while len(h) > 0:
		z = heapq.heappop(h)
		print(z)
		a.append(z)
	for z in a:
		heapq.heappush(h, z)
(n, m) = inm()
a = []
for i in range(m):
	(l, r, c) = inm()
	a.append((l, r, c))
a.sort()
if a[0][0] > 1:
	print(-1)
	exit()
ddprint(a)
h = []
top = 0
for i in range(m):
	(l, r, c) = a[i]
	if l == 1:
		heapq.heappush(h, (c, 0, l, r, c))
	else:
		top = i
		break
if DBG:
	dumpheap(h)
(curld, curd, curl, curr, curc) = heapq.heappop(h)
for i in range(top, m):
	(l, r, c) = a[i]
	while curr < l:
		if len(h) == 0:
			print(-1)
			exit()
		(curld, curd, curl, curr, curc) = heapq.heappop(h)
	heapq.heappush(h, (curld, curd, curl, curr, curc))
	heapq.heappush(h, (curld + c, curld, l, r, c))
r = 0
while r < n:
	if len(h) == 0:
		print(-1)
		exit()
	(ld, d, l, r, c) = heapq.heappop(h)
print(ld)


from heapq import heappop, heappush
(N, M) = map(int, input().split())
route_list = [[] for _ in range(N)]
for i in range(M):
	(L, R, C) = map(int, input().split())
	route_list[L - 1].append((R - 1, C))
for i in range(N - 1):
	route_list[i + 1].append((i, 0))
distance = [float('inf')] * N
distance[0] = 0
q = [(0, 0)]
while q:
	(_, u) = heappop(q)
	for (des, cost) in route_list[u]:
		if distance[des] > distance[u] + cost:
			distance[des] = distance[u] + cost
			heappush(q, (distance[des], des))
print(distance[-1] if distance[-1] != float('inf') else -1)


(n, m) = map(int, input().split())
lrc = [list(map(int, input().split())) for _ in range(m)]
lrc.sort(key=lambda x: x[0])
inf = float('inf')
seen = [inf] * n
seen[0] = 0
now = 0
from heapq import heappop, heappush
from collections import deque
lrc = deque(lrc)
todo = [[0, now]]
while todo:
	(d, v) = heappop(todo)
	lst = []
	while lrc and lrc[0][0] <= v + 1:
		lst.append(lrc.popleft())
	for (l, r, c) in lst:
		if seen[r - 1] > seen[v] + c:
			heappush(todo, [seen[v] + c, r - 1])
			seen[r - 1] = seen[v] + c
if seen[-1] != inf:
	print(seen[-1])
else:
	print(-1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
t = sorted([tuple(map(int, input().split())) for i in range(m)])
INF = 10 ** 18
dp = [0, 0] + [INF] * (n - 1)
for (l, r, c) in t:
	for i in range(r, l, -1):
		if dp[l] + c < dp[i]:
			dp[i] = dp[l] + c
		else:
			break
ans = dp[n]
if ans == INF:
	print(-1)
else:
	print(ans)


import sys
from heapq import *
input = sys.stdin.readline

def main():
	(n, m) = map(int, input().split())
	tree = [[] for _ in range(n)]
	for i in range(m):
		(s, t, c) = map(int, input().split())
		tree[t - 1].append((s - 1, c))
		tree[s - 1].append((t - 1, c))
	for i in range(n - 1):
		tree[i + 1].append((i, 0))
	ans = [-1] * n
	already = [False] * n
	not_yet = [(0, 0)]
	while not_yet:
		(value, key) = heappop(not_yet)
		if already[key]:
			continue
		already[key] = True
		ans[key] = value
		for (k, v) in tree[key]:
			if already[k]:
				continue
			heappush(not_yet, (v + value, k))
	print(ans[n - 1])
main()


import sys
from heapq import heapify, heappop, heappush
MAX_INT = int(1e+16)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)

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

def SL():
	return input().split()

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

def S():
	return input()
(N, M) = IL()
LRC = [IL() for _ in range(M)]
root = [[(0, i - 1)] for i in range(N + 1)]
for i in range(M):
	(L, R, C) = LRC[i]
	root[L].append((C, R))
data = []
heappush(data, (0, 1))
ans = [MAX_INT] * (N + 1)
ans[1] = 0
finished = [False] * (N + 1)
finished[0] = True
while data:
	(nowcost, v) = heappop(data)
	if finished[v] == False:
		finished[v] = True
		for (edge, nextv) in root[v]:
			if ans[nextv] < nowcost + edge:
				continue
			else:
				ans[nextv] = nowcost + edge
				heappush(data, (nowcost + edge, nextv))
if finished[N] == True:
	print(ans[N])
else:
	print(-1)


from heapq import *

def Dijkstra(G: list, source=0):
	INF = float('inf')
	V = len(G)
	D = [INF] * V
	vis = [False] * V
	H = [(0, source)]
	while H:
		(dist, cur) = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for (nxt, cost) in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D[-1] if D[-1] != INF else -1
(N, M, *L) = map(int, open(0).read().split())
G = [[(i - 1, 0)] for i in range(N)]
G[0] = []
for (l, r, c) in zip(*[iter(L)] * 3):
	G[l - 1].append((r - 1, c))
print(Dijkstra(G))


import heapq
(n, m) = map(int, input().split())
INF = float('inf')

def dijkstra(s, n, edges):
	d = [INF] * n
	d[s] = 0
	pq = [(0, s)]
	while len(pq) != 0:
		(c, v) = heapq.heappop(pq)
		if d[v] < c:
			continue
		for (v2nvc, nv) in edges[v]:
			if c + v2nvc < d[nv]:
				d[nv] = c + v2nvc
				heapq.heappush(pq, (d[nv], nv))
	return d
edges = [[] for _ in range(n)]
for _ in range(m):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	edges[l].append((c, r))
for i in range(n - 1):
	edges[i + 1].append((0, i))
d = dijkstra(0, n, edges)
if d[-1] == INF:
	print(-1)
else:
	print(d[-1])


from heapq import heappush, heappop

def dijkstra(graph: list, node: int, start: int) -> list:
	inf = float('inf')
	dist = [inf] * node
	dist[start] = 0
	heap = [(0, start)]
	while heap:
		(cost, thisNode) = heappop(heap)
		for (NextCost, NextNode) in graph[thisNode]:
			dist_cand = dist[thisNode] + NextCost
			if dist_cand < dist[NextNode]:
				dist[NextNode] = dist_cand
				heappush(heap, (dist[NextNode], NextNode))
	return dist
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(N - 1):
	graph[i + 1].append((0, i))
for i in range(M):
	(L, R, C) = map(int, input().split())
	graph[L - 1].append((C, R - 1))
	graph[R - 1].append((C, L - 1))
d = dijkstra(graph, N, 0)
ans = d[-1] if d[-1] != float('inf') else -1
print(ans)


import heapq
(N, M) = map(int, input().split())
items = []
for _ in range(M):
	(l, r, c) = map(int, input().split())
	items.append([l, r, c])
items.sort()

def check():
	queue = []
	index = 0
	data = [None]
	dists = [None, 0]
	for i in range(1, N):
		while index < M:
			(l, r, c) = items[index]
			if l <= i:
				heapq.heappush(queue, (c + dists[i], -r))
				index += 1
			else:
				break
		while True:
			if len(queue) == 0:
				return None
			(c, r) = queue[0]
			if -r > i:
				break
			heapq.heappop(queue)
		data.append((c, -r))
		dists.append(c)
	return dists
data = check()
if data != None:
	print(data[N])
else:
	print(-1)


from collections import deque
import heapq
(N, M) = map(int, input().split())
LRC2 = []
for i in range(M):
	(L, R, C) = map(int, input().split())
	L -= 1
	R -= 1
	LRC2.append([L, R, C])
LRC2.sort()
LRC = deque([])
for i in LRC2:
	LRC.append(i)
q = []
for i in range(N):
	while len(LRC) > 0 and LRC[0][0] == i:
		now = LRC.popleft()
		L = now[0]
		C = now[2]
		R = now[1]
		if L == 0:
			heapq.heappush(q, [C, R])
			continue
		while len(q) > 0 and q[0][1] < i:
			heapq.heappop(q)
		if len(q) > 0:
			heapq.heappush(q, [C + q[0][0], R])
while len(q) > 0 and q[0][1] < N - 1:
	heapq.heappop(q)
if len(q) > 0:
	print(q[0][0])
else:
	print(-1)


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

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

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

def dijkstra(s, graph):
	d = [inf] * n
	d[s] = 0
	h = [(0, s)]
	while h:
		(c, v) = heappop(h)
		if d[v] < c:
			continue
		for (t, cost) in graph[v]:
			if d[v] + cost < d[t]:
				d[t] = d[v] + cost
				heappush(h, (d[t], t))
	return d
(n, m) = LI()
lrc = [LI() for _ in range(m)]
edge = [[] for _ in range(n)]
for (l, r, c) in lrc:
	edge[l - 1].append((r - 1, c))
for i in range(n - 1):
	edge[i + 1].append((i, 0))
d = dijkstra(0, edge)
if d[-1] == inf:
	print(-1)
else:
	print(d[-1])


import sys, heapq
input = sys.stdin.readline
(n, m) = map(int, input().split())
Ad = [[] for _ in range(n)]
for i in range(m):
	(li, ri, ci) = map(int, input().split())
	Ad[li - 1].append((ri - 1, ci))
for i in range(1, n):
	Ad[i].append((i - 1, 0))
inf = 10 ** 20
D = [inf for _ in range(n)]
D[0] = 0
Q = []
heapq.heappush(Q, (0, 0))
while Q:
	(d, q) = heapq.heappop(Q)
	for (v, c) in Ad[q]:
		if D[v] > d + c:
			D[v] = d + c
			heapq.heappush(Q, (d + c, v))
if D[n - 1] < inf:
	print(D[n - 1])
else:
	print(-1)


class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	def E(self):
		return self._E

	def V(self):
		return self._V

	def add(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [float('inf')] * self._V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while que:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d
(n, m) = map(int, input().split())
g = Dijkstra(n)
for i in range(1, n):
	g.add(i, i - 1, 0)
for i in range(m):
	(u, v, c) = map(int, input().split())
	if u > v:
		(u, v) = (v, u)
	g.add(u - 1, v - 1, c)
tmp = g.shortest_path(0)[-1]
if tmp == float('inf'):
	print(-1)
else:
	print(tmp)


import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
(N, M) = map(int, input().split())
a = []
e = dd(list)
s = []
for _ in range(M):
	a.append(list(map(int, input().split())))
	e[a[-1][0]].append((a[-1][1], a[-1][2]))
a.sort(key=lambda x: (x[0], x[1]))
x = 0
for i in range(1, N):
	e[i + 1].append((i, 0))

class dijkstra:

	def __init__(self, n, e):
		self.e = e
		self.n = n

	def path(self, s, t):
		d = [float('inf')] * (self.n + 1)
		vis = set()
		d[s] = 0
		h = [s]
		while not t in vis and len(h):
			v = heapq.heappop(h)
			v1 = v % 10 ** 10
			v0 = v // 10 ** 10
			if v1 in vis:
				continue
			vis.add(v1)
			for p in self.e[v1]:
				d[p[0]] = min(d[p[0]], d[v1] + p[1])
				if p[0] in vis:
					continue
				heapq.heappush(h, d[p[0]] * 10 ** 10 + p[0])
		return d[t]
d = dijkstra(N, e)
res = d.path(1, N)
if res == float('inf'):
	print(-1)
else:
	print(res)


import heapq

def dijkstra_heap(s, g):
	used = [True] * n
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, [e[0], e[1]])
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		if v == g:
			return minedge[0]
		kai = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, [kai + e[0], e[1]])
	return -1
(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
l = []
for i in range(m):
	(x, y, z) = map(int, input().split())
	edge[x - 1].append([z, y - 1])
	edge[y - 1].append([z, x - 1])
	l.append([x - 1, y - 1])
zeroedge = [0] * n
l.sort()
l.append([10 ** 10, 10 ** 10 + 1])
i = 0
nl = l[i][0]
r = l[i][1]
while i < m + 1:
	if l[i][0] > r:
		for j in range(nl, r):
			edge[j + 1].append([0, j])
		nl = l[i][0]
		r = l[i][1]
		i += 1
	else:
		r = max(r, l[i][1])
		i += 1
print(dijkstra_heap(0, n - 1))


import sys
from heapq import heapify, heappop, heappush
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))

def dijkstra(start):
	dist = [INF] * (N + 1)
	dist[start] = 0
	que = [(0, start)]
	while que:
		(d, prev) = heappop(que)
		if dist[prev] < d:
			continue
		for (cost, next) in graph[prev]:
			d1 = d + cost
			if dist[next] > d1:
				dist[next] = d1
				heappush(que, (d1, next))
	return dist
(N, M) = lr()
INF = 10 ** 15
graph = [[] for _ in range(N + 1)]
for i in range(2, N + 1):
	graph[i].append((0, i - 1))
for _ in range(M):
	(l, r, c) = lr()
	graph[l].append((c, r))
dist = dijkstra(1)
if dist[N] == INF:
	print(-1)
else:
	print(dist[N])


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

def dijkstra(graph: list, n: int, v_s: int, INF: int=float('inf')) -> list:
	dist = [INF] * n
	dist[v_s] = 0
	heap = [(0, v_s)]
	while heap:
		(_, v_from) = heappop(heap)
		for (cost, v_to) in graph[v_from]:
			dist_cand = dist[v_from] + cost
			if dist_cand < dist[v_to]:
				dist[v_to] = dist_cand
				heappush(heap, (dist[v_to], v_to))
	return dist
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	edge[l].append((c, r))
for i in range(1, n):
	edge[i].append((0, i - 1))
dist = dijkstra(edge, n, 0)
ans = dist[-1] if dist[-1] != float('inf') else -1
print(ans)


from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)

def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
(N, M) = map(int, input().split())
LRC = [list(map(int, input().split())) for i in range(M)]
LRC.sort()
stack = [[0, -1, 0]]
idle_max = 10 ** 18
visited = [idle_max for i in range(N + 1)]
visited2 = [0 for i in range(N + 1)]
visited[1] = 0
x = 0
while stack:
	(m, a, p) = heappop(stack)
	a = -a
	if a == N:
		print(m)
		break
	if not visited2[a]:
		visited2[a] = 1
		for i in range(x, M):
			(l, r, c) = LRC[i]
			x = i
			if l <= a:
				_m = m + c
				if _m < visited[r]:
					visited[r] = _m
					heappush(stack, [_m, -r, a + 1])
			else:
				break
else:
	print(-1)


import heapq
(n, m) = [int(v) for v in input().split(' ')]
links = []
for i in range(n):
	links.append([])
for i in range(m):
	(l, r, c) = [int(v) for v in input().split(' ')]
	l -= 1
	r -= 1
	links[r].append((l, c))
h = []
heapq.heappush(h, (0, n - 1))
closed = 0
while len(h) > 0:
	(c0, n0) = heapq.heappop(h)
	if closed & 1 << n0 != 0:
		continue
	closed |= 1 << n0
	if n0 == 0:
		print(c0)
		exit()
	for (n1, c1) in links[n0]:
		if closed & 1 << n1 != 0:
			continue
		heapq.heappush(h, (c0 + c1, n1))
	n2 = n0 + 1
	if n2 < n:
		if closed & 1 << n2 == 0:
			heapq.heappush(h, (c0, n2))
print('-1')


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
LRC = [tuple(map(int, input().split())) for i in range(M)]
LRC.sort()
INF = float('inf')

class SegTreeMin:

	def __init__(self, arr):
		n = 1
		while n < len(arr):
			n *= 2
		self.n = n
		nodes = [INF] * (2 * n - 1)
		nodes[n - 1:n - 1 + len(arr)] = arr
		for i in range(n - 2, -1, -1):
			nodes[i] = min(nodes[2 * i + 1], nodes[2 * i + 2])
		self.nodes = nodes

	def update(self, i, val):
		i += self.n - 1
		self.nodes[i] = val
		while i >= 0:
			i = (i - 1) // 2
			self.nodes[i] = min(self.nodes[2 * i + 1], self.nodes[2 * i + 2])

	def query(self, l, r):
		L = l + self.n
		R = r + self.n
		s = INF
		while L < R:
			if R & 1:
				R -= 1
				s = min(s, self.nodes[R - 1])
			if L & 1:
				s = min(s, self.nodes[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s
segt = SegTreeMin([0] + [INF] * N)
for (l, r, c) in LRC:
	mn = segt.query(l - 1, r - 1)
	org = segt.query(r - 1, r)
	if org > mn + c:
		segt.update(r - 1, mn + c)
ans = segt.query(N - 1, N)
print(-1 if ans == INF else ans)


import heapq
(N, M) = map(int, input().split())
LRC = [tuple(map(int, input().split())) for i in range(M)]
es = [[] for i in range(N)]
for (l, r, c) in LRC:
	(l, r) = (l - 1, r - 1)
	es[l].append((r, c))
for i in range(N - 1):
	es[i + 1].append((i, 0))
INF = float('inf')
dist = [INF] * N
dist[0] = 0
hq = [(0, 0)]
heapq.heapify(hq)
while hq:
	(d, v) = heapq.heappop(hq)
	if v == N - 1:
		print(d)
		exit()
	for (to, c) in es[v]:
		if d + c >= dist[to]:
			continue
		dist[to] = d + c
		heapq.heappush(hq, (d + c, to))
print(-1)


from heapq import heappop, heappush
(N, M) = map(int, input().split())
V = [[] for _ in range(N)]
for i in range(1, N):
	V[i].append((i - 1, 0))
for _ in range(M):
	(l, r, c) = map(int, input().split())
	V[l - 1].append((r - 1, c))
INF = float('inf')
q = [(0, 0)]
d = [INF] * N
d[0] = 0
while q:
	(_, u) = heappop(q)
	for (v, c) in V[u]:
		if d[v] > d[u] + c:
			d[v] = d[u] + c
			heappush(q, (d[v], v))
print(d[-1] if d[-1] != INF else -1)


from heapq import heappush, heappop

def dijkstra(edges, size, source):
	distance = [float('inf')] * size
	distance[source] = 0
	visited = [False] * size
	pq = []
	heappush(pq, (0, source))
	while pq:
		(dist_v, v) = heappop(pq)
		visited[v] = True
		for (u, weight) in edges[v]:
			if not visited[u]:
				new_dist = dist_v + weight
				if distance[u] > new_dist:
					distance[u] = new_dist
					heappush(pq, (new_dist, u))
	return distance[n - 1]
(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)]
for i in range(m):
	b[a[i][0] - 1].append((a[i][1] - 1, a[i][2]))
for i in range(n - 1):
	b[i + 1].append((i, 0))
x = dijkstra(b, n, 0)
if x == float('inf'):
	print(-1)
else:
	print(x)


import heapq

def dijkstra(s, path):
	inf = float('inf')
	n = len(path)
	d = [inf for i in range(n)]
	d[s] = 0
	q = [(0, s)]
	heapq.heapify(q)
	while q:
		(c, p) = heapq.heappop(q)
		if d[p] < c:
			continue
		for (cost, to) in path[p]:
			if d[to] > d[p] + cost:
				d[to] = d[p] + cost
				heapq.heappush(q, (d[to], to))
	return d
(n, m) = map(int, input().split())
path = [[] for i in range(n)]
for i in range(n - 1):
	path[i + 1].append([0, i])
for i in range(m):
	(l, r, c) = map(int, input().split())
	path[l - 1].append([c, r - 1])
ans = dijkstra(0, path)[-1]
print(-1 if ans == float('inf') else ans)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	(n, m) = map(int, input().split())
	E = [[] for _ in range(n)]
	for i in range(1, n):
		E[i].append((i - 1, 0))
	for _ in range(m):
		(l, r, c) = map(int, input().split())
		l -= 1
		r -= 1
		E[l].append((r, c))
	from heapq import heappop, heappush
	Q = [(0, 0)]
	dist = [INF] * n
	dist[0] = 0
	while Q:
		(d, v) = heappop(Q)
		if dist[v] < d:
			continue
		for (nv, w) in E[v]:
			if dist[nv] > dist[v] + w:
				dist[nv] = dist[v] + w
				heappush(Q, (dist[nv], nv))
	ans = dist[-1]
	if ans == INF:
		ans = -1
	print(ans)
resolve()


from collections import *
from fractions import gcd
from functools import *
from itertools import *
from operator import mul, itemgetter
from bisect import *
from heapq import *
from math import factorial, pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
(n, m) = map(int, input().split())

def DIJKSTRA(point, d):
	cost = [float('inf')] * (n + 1)
	Q = []
	cost[point] = 0
	heappush(Q, (point, cost[point]))
	while Q:
		(prefnd, tmpC) = heappop(Q)
		if cost[prefnd] < tmpC:
			continue
		for (node, c) in d[prefnd]:
			altC = c + tmpC
			if cost[node] > altC:
				cost[node] = altC
				heappush(Q, (node, altC))
	return cost

def main():
	d = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b, c) = map(int, input().split())
		d[a].append((b, c))
	for i in range(1, n + 1):
		d[i].append((i - 1, 0))
	x = DIJKSTRA(1, d)[n]
	if x != float('inf'):
		print(x)
	else:
		print(-1)
main()


INFTY = 10 ** 14 + 5
(N, M) = map(int, input().split())
A = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
A = sorted(A, key=lambda x: x[0])
d = [INFTY for _ in range(N + 1)]
d[1] = 0
for i in range(M):
	(L, R, C) = A[i]
	d[R] = min(d[R], d[L] + C)
	j = R - 1
	while d[j] > d[R]:
		d[j] = d[R]
		j -= 1
if d[N] >= INFTY:
	print(-1)
else:
	print(d[N])


import heapq

def main():
	(n, m) = map(int, input().split())
	dics = [{} for _ in range(n)]
	for _ in range(m):
		(l, r, c) = map(int, input().split())
		ky = r - 1
		if ky in dics[l - 1]:
			if c < dics[l - 1][ky]:
				dics[l - 1][ky] = c
		else:
			dics[l - 1][ky] = c
	dist = [float('inf')] * n
	dist[0] = 0
	hq = []
	heapq.heappush(hq, [0, 0])
	idx = 0
	while len(hq) > 0:
		(v, p) = heapq.heappop(hq)
		if p < idx:
			continue
		if p == n - 1:
			break
		for i in range(idx + 1, p):
			if len(dics[i]) > 0:
				for ky in dics[i].keys():
					if ky in dics[p]:
						if dics[p][ky] > dics[i][ky]:
							dics[p][ky] = dics[i][ky]
					elif p < ky:
						dics[p][ky] = dics[i][ky]
		idx = p
		for r in dics[p].keys():
			if dist[r] > v + dics[p][r]:
				dist[r] = v + dics[p][r]
				heapq.heappush(hq, [v + dics[p][r], r])
	if dist[n - 1] == float('inf'):
		print(-1)
	else:
		print(dist[n - 1])
main()


import sys
input = sys.stdin.readline
import heapq as hp
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(l, r, c) = map(int, input().split())
	graph[l - 1].append((c, r - 1))
for i in range(N - 1):
	graph[i + 1].append((0, i))
INF = 10 ** 16
D = [INF for _ in range(N)]
D[0] = 0
q = []
hp.heappush(q, (0, 0))
while q:
	(nd, np) = hp.heappop(q)
	if D[np] < nd:
		continue
	for (d, p) in graph[np]:
		if D[p] > D[np] + d:
			D[p] = D[np] + d
			hp.heappush(q, (D[p], p))
d = D[-1]
if d == INF:
	print(-1)
else:
	print(d)


import sys
from heapq import heappush, heappop, heapify
read = sys.stdin.readline
INF = 10 ** 30

def dijkstra(G, s, n):
	que = [(0, s)]
	dist = [INF] * n
	dist[s] = 0
	while que:
		(mincost, u) = heappop(que)
		if mincost > dist[u]:
			continue
		for (c, v) in G[u]:
			if dist[u] + c < dist[v]:
				dist[v] = dist[u] + c
				heappush(que, (dist[v], v))
	return dist
(N, M) = map(int, read().split())
G = [[] for _ in range(N)]
for i in range(N - 1):
	G[i + 1].append((0, i))
for i in range(M):
	(L, R, C) = map(int, read().split())
	L -= 1
	R -= 1
	G[L].append((C, R))
dist = dijkstra(G, 0, N)
ans = dist[N - 1]
print(ans if ans != INF else -1)


from heapq import heappop, heappush
(N, M) = map(int, input().split())
adj = [[] for _ in range(N)]
for i in range(N - 1):
	adj[i + 1].append((i, 0))
for i in range(M):
	(L, R, C) = map(int, input().split())
	adj[L - 1].append((R - 1, C))
q = []
heappush(q, 0)
INF = 10 ** 18
d = [INF] * N
d[0] = 0
while len(q) > 0:
	u = heappop(q)
	for v in adj[u]:
		tmp = d[u] + v[1]
		if tmp < d[v[0]]:
			d[v[0]] = tmp
			heappush(q, v[0])
print(d[N - 1]) if d[N - 1] < INF else print(-1)


NN = 17
MI = [1 << 100] * ((1 << NN + 1) - 1)

def update(a, x):
	i = (1 << NN) - 1 + a
	MI[i] = min(MI[i], x)
	while True:
		i = (i - 1) // 2
		MI[i] = min(MI[2 * i + 1], MI[2 * i + 2])
		if i == 0:
			break

def rangemin(a):
	l = a + (1 << NN)
	r = (1 << NN + 1) - 2
	mi = 1 << 100
	while l < r:
		if l % 2:
			mi = min(mi, MI[l - 1])
			l += 1
		if r % 2:
			r -= 1
			mi = min(mi, MI[r - 1])
		l >>= 1
		r >>= 1
	return mi
(N, M) = map(int, input().split())
X = []
for _ in range(M):
	(l, r, c) = map(int, input().split())
	X.append((l, r, c))
X = sorted(X)
update(1, 0)
for (l, r, c) in X:
	mi = rangemin(l)
	update(r, mi + c)
ans = MI[(1 << NN) - 1 + N]
print(ans if ans < 1 << 100 else -1)


(n, m) = map(int, input().split())
lst = []
for i in range(m):
	lsti = list(map(int, input().split()))
	lst.append(lsti)
lst.sort(key=lambda x: x[2], reverse=True)
lst.sort(key=lambda x: x[0])
d = [10 ** 18 for i in range(n + 1)]
d[1] = 0
for lsti in lst:
	l = lsti[0]
	r = lsti[1]
	c = lsti[2]
	if l == 1:
		for i in range(l + 1, r + 1):
			d[i] = c
	else:
		for i in range(l + 1, r + 1):
			j = l + 1 + r - i
			if d[l] + c < d[j]:
				d[j] = d[l] + c
			else:
				break
if d[n] == 10 ** 18:
	print(-1)
else:
	print(d[n])


from heapq import heappop, heappush
(n, m) = map(int, input().split())
g = [[] for __ in range(n)]
for _ in range(m):
	(l, r, c) = map(int, input().split())
	g[l - 1].append((r - 1, c))
for i in range(1, n):
	g[i].append((i - 1, 0))
d = [10 ** 18] * n
d[0] = 0
q = [(0, 0)]
while q:
	(dist_u, u) = heappop(q)
	if d[u] < dist_u:
		continue
	for (v, c) in g[u]:
		if d[v] > dist_u + c:
			d[v] = dist_u + c
			heappush(q, (d[v], v))
print(d[n - 1] if d[n - 1] != 10 ** 18 else -1)


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

def Dijkstra(adjList, vSt):
	numV = len(adjList)
	numUsed = 0
	costs = [INF] * numV
	costs[vSt] = 0
	PQ = []
	heappush(PQ, (0, vSt))
	while PQ:
		(cNow, vNow) = heappop(PQ)
		if cNow > costs[vNow]:
			continue
		numUsed += 1
		if numUsed == numV:
			break
		for (v2, wt) in adjList[vNow]:
			c2 = cNow + wt
			if c2 < costs[v2]:
				costs[v2] = c2
				heappush(PQ, (c2, v2))
	return costs
(N, M) = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
	(L, R, C) = map(int, input().split())
	(L, R) = (L - 1, R - 1)
	adjL[L].append((R, C))
	adjL[R].append((L, C))
for i in range(N - 1):
	adjL[i + 1].append((i, 0))
costs = Dijkstra(adjL, 0)
if costs[-1] == INF:
	print(-1)
else:
	print(costs[-1])


(n, m, *t) = map(int, open(0).read().split())
inf = float('inf')
dp = [inf] * -~n
dp[1] = 0
import heapq
mn = []
path = eval('[],' * -~n)
for (l, r, c) in zip(*[iter(t)] * 3):
	path[l].append((r, c))

def ins(v, r):
	heapq.heappush(mn, (v, r))
for i in range(1, n + 1):
	while len(mn) and mn[0][1] < i:
		heapq.heappop(mn)
	if len(mn):
		dp[i] = min(dp[i], mn[0][0])
	for (r, c) in path[i]:
		ins(dp[i] + c, r)
if dp[n] == inf:
	print(-1)
else:
	print(dp[n])


from heapq import *
from collections import *
(N, M) = map(int, input().split())
(L, R, C) = ([0] * M, [0] * M, [0] * M)
for i in range(M):
	(L[i], R[i], C[i]) = map(int, input().split())
	L[i] -= 1
	R[i] -= 1
start = defaultdict(lambda : [])
end = defaultdict(lambda : [])
for i in range(M):
	start[L[i]].append(i)
	end[R[i]].append(i)
state = []
for i in start[0]:
	heappush(state, (C[i], i))
for i in range(1, N):
	while len(state) > 0 and R[state[0][1]] < i:
		heappop(state)
	if len(state) == 0:
		print(-1)
		exit()
	for j in start[i]:
		heappush(state, (state[0][0] + C[j], j))
print(state[0][0])


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

def dijkstra1(V, n, inf, source):
	dist = [inf] * (n + 1)
	dist[source] = 0
	q = [(0, source)]
	while q:
		(cost, u) = heappop(q)
		if dist[u] < cost:
			continue
		for (c, v) in V[u]:
			if dist[v] > dist[u] + c:
				dist[v] = dist[u] + c
				heappush(q, (dist[v], v))
	return dist

def solve():
	(N, M) = map(int, input().split())
	INF = 10 ** 20
	l = []
	V = defaultdict(list)
	for _ in range(M):
		(L, R, C) = map(int, input().split())
		V[L].append((C, R))
	for i in range(1, N):
		V[i + 1].append((0, i))
	dj = dijkstra1(V, N, INF, 1)
	print(dj[N] if dj[N] != INF else -1)
solve()


import heapq
(n, m) = [int(i) for i in input().split()]
lrc = []
for _ in range(m):
	(l, r, c) = [int(i) for i in input().split()]
	lrc.append([l - 1, r - 1, c])
lrc.sort()
a = []
j = 0
for i in range(n - 1):
	new = []
	while j < m and lrc[j][0] == i:
		new.append(lrc[j])
		j += 1
	if i == 0:
		now = 0
	else:
		while True:
			if len(a) == 0:
				print(-1)
				exit()
			now = heapq.heappop(a)
			if now[1] >= i:
				heapq.heappush(a, now)
				break
		now = now[0]
	for k in new:
		heapq.heappush(a, [now + k[2], k[1]])
while True:
	if len(a) == 0:
		print(-1)
		exit()
	now = heapq.heappop(a)
	if now[1] >= n - 1:
		heapq.heappush(a, now)
		break
now = now[0]
print(now)


from heapq import heappop, heappush
(n, m) = map(int, input().split())
graph = [list() for _ in range(n)]
for i in range(1, n):
	graph[i].append((i - 1, 0))
for _ in range(m):
	(f, t, c) = map(int, input().split())
	f -= 1
	t -= 1
	graph[f].append((t, c))
INF = float('inf')
s = 0
d = [0] + [INF] * (n - 1)
q = []
heappush(q, (0, s))
while q:
	(dist, v) = heappop(q)
	if d[v] < dist:
		continue
	for (nv, cost) in graph[v]:
		if d[nv] > d[v] + cost:
			d[nv] = d[v] + cost
			heappush(q, (d[nv], nv))
print(-1 if d[n - 1] == INF else d[n - 1])


def main():
	(n, m) = map(int, input().split())
	lrc = [tuple(map(int, input().split())) for _ in range(m)]
	lcr = sorted([(i[0] - 1, i[2], i[1] - 1) for i in lrc], reverse=True)
	INF = float('inf')
	dist = [INF] * n
	check = [False] * n
	check[0] = True
	dist[0] = 0
	enable = True
	while lcr:
		route = lcr.pop(-1)
		mn = route[0]
		mx = route[-1]
		if not check[mn]:
			enable = False
			break
		else:
			d = route[1] + dist[mn]
			for i in range(mx, mn, -1):
				if dist[i] >= d:
					dist[i] = d
					check[i] = True
				else:
					break
	if dist[-1] == INF:
		print(-1)
	elif enable:
		print(dist[-1])
	else:
		print(-1)
main()


import sys
input = sys.stdin.readline
import heapq

def main():
	(N, M) = map(int, input().split())
	INF = 10 ** 15
	root = [[] for _ in range(N)]
	for i in range(N - 1):
		root[i + 1].append((0, i))
	for _ in range(M):
		(l, r, c) = map(int, input().split())
		root[l - 1].append((c, r - 1))
	dist = [INF for _ in range(N)]
	q = [(0, 0)]
	dist[0] = 0
	while q:
		(d, now) = heapq.heappop(q)
		if dist[now] < d:
			continue
		for (cost, fol) in root[now]:
			_d = d + cost
			if dist[fol] > _d:
				dist[fol] = _d
				heapq.heappush(q, (_d, fol))
	if dist[-1] == INF:
		print(-1)
	else:
		print(dist[-1])
main()


from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
INF = float('inf')

def solve():
	(N, M) = map(int, input().split())
	Es = []
	for _ in range(M):
		(L, R, C) = map(int, input().split())
		(L, R) = (L - 1, R - 1)
		Es.append((L, R, C))
	Es.sort()
	PQ = [(0, 0)]
	dists = [INF] * N
	iE = 0
	for tm in range(N):
		while PQ:
			(dist, R) = PQ[0]
			if tm <= R:
				break
			heappop(PQ)
		else:
			return -1
		dists[tm] = dist
		while iE < M and Es[iE][0] == tm:
			(L, R, C) = Es[iE]
			heappush(PQ, (dist + C, R))
			iE += 1
	return dists[-1]
print(solve())


import sys
import heapq
input = sys.stdin.readline

def dijkstra(s, E):
	inf = float('inf')
	d = [inf for i in range(len(E))]
	d[s] = 0
	q = [(0, s)]
	while q:
		(c, p) = heapq.heappop(q)
		if d[p] < c:
			continue
		for (cost, to) in E[p]:
			if d[to] > d[p] + cost:
				d[to] = d[p] + cost
				heapq.heappush(q, (d[to], to))
	return d

def main():
	(N, M) = map(int, input().split())
	E = [[] for _ in range(N)]
	for _ in range(M):
		(s, t, c) = map(int, input().split())
		E[s - 1].append((c, t - 1))
	for i in range(N - 1):
		E[i + 1].append((0, i))
	A = dijkstra(0, E)
	ans = A[N - 1]
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)
main()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(n, m) = map(int, readline().split())
chk = []
for i in range(m):
	(l, r, c) = map(int, readline().split())
	chk.append((l - 1, r - 1, c))
chk.sort()

class SegmentTree:

	def __init__(self, n, ele, segfun):
		self.ide_ele = ele
		self.segfun = segfun
		self.n = n
		self.N0 = 1 << n.bit_length()
		self.data = [self.ide_ele] * (self.N0 * 2)

	def update(self, l, r, val):
		l += self.N0
		r += self.N0
		while l < r:
			if l & 1:
				self.data[l] = self.segfun(self.data[l], val)
				l += 1
			if r & 1:
				self.data[r - 1] = self.segfun(self.data[r - 1], val)
				r -= 1
			l //= 2
			r //= 2

	def query(self, i):
		i += len(self.data) // 2
		ret = self.data[i]
		while i > 0:
			i //= 2
			ret = self.segfun(ret, self.data[i])
		return ret
S = SegmentTree(n, 10 ** 14, lambda a, b: min(a, b))
S.update(0, 1, 0)
for (l, r, c) in chk:
	a = S.query(l)
	S.update(l, r + 1, a + c)
ans = S.query(n - 1)
if ans == 10 ** 14:
	print(-1)
else:
	print(ans)


from bisect import bisect_left
(N, M) = map(int, input().split())
LRC = []
for _ in range(M):
	(L, R, C) = map(int, input().split())
	LRC.append((L - 1, R - 1, C))
LRC.sort()
LRC.sort(key=lambda x: x[1])
cost_r = [0]
cost_v = [0]
for (L, R, C) in LRC:
	i = bisect_left(cost_r, L)
	if i == len(cost_r):
		continue
	nc = cost_v[i] + C
	while nc < cost_v[-1]:
		cost_r.pop()
		cost_v.pop()
	if R > cost_r[-1]:
		cost_r.append(R)
		cost_v.append(nc)
if cost_r[-1] == N - 1:
	print(cost_v[-1])
else:
	print(-1)


(n, m) = map(int, input().split())
graph = {i: {} for i in range(1, n + 1)}
for i in range(1, n):
	graph[i + 1][i] = 0
for _ in range(m):
	(l, r, c) = map(int, input().split())
	if not r in graph[l].keys():
		graph[l][r] = c
	else:
		graph[l][r] = min(graph[l][r], c)
import heapq

def dijkstra(s, graph, n):
	dist = [10 ** 20 for i in range(n + 1)]
	dist[s] = 0
	pq = []
	heapq.heapify(pq)
	heapq.heappush(pq, (0, s))
	while pq:
		x = heapq.heappop(pq)
		(node, mini_dis) = (x[1], x[0])
		for point in graph[node].keys():
			w = graph[node][point]
			newlen = dist[node] + w
			if newlen < dist[point]:
				heapq.heappush(pq, (newlen, point))
				dist[point] = newlen
	return dist
A = dijkstra(1, graph, n)
if A[n] < 10 ** 20:
	print(A[n])
else:
	print(-1)


import heapq
import sys
input = sys.stdin.readline

def dijkstra_heap(s, edge):
	d = [float('inf')] * n
	used = [True] * n
	d[s] = 0
	used[s] = False
	edgelist = []
	for (a, b) in edge[s]:
		heapq.heappush(edgelist, a * 10 ** 6 + b)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge % 10 ** 6]:
			continue
		v = minedge % 10 ** 6
		d[v] = minedge // 10 ** 6
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, (e[0] + d[v]) * 10 ** 6 + e[1])
	return d
(n, w) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(n - 1):
	edge[i + 1].append([0, i])
for i in range(w):
	(x, y, z) = map(int, input().split())
	edge[x - 1].append([z, y - 1])
	edge[y - 1].append([z, x - 1])
ret = dijkstra_heap(0, edge)[-1]
if ret == float('inf'):
	ret = -1
print(ret)


import heapq
import collections

def main():
	(N, M) = map(int, input().split())
	graph = collections.defaultdict(dict)
	for i in range(N - 1):
		graph[i + 1][i] = 0
	for _ in range(M):
		(L, R, C) = map(int, input().split())
		if L - 1 in graph and R - 1 in graph[L - 1]:
			graph[L - 1][R - 1] = min(graph[L - 1][R - 1], C)
		else:
			graph[L - 1][R - 1] = C
	dist = [float('inf') for _ in range(N)]
	dist[0] = 0
	v = []
	heapq.heappush(v, [0, 0])
	while len(v) > 0:
		(d, u) = heapq.heappop(v)
		if d > dist[u]:
			continue
		for w in graph[u]:
			if dist[w] > d + graph[u][w]:
				dist[w] = d + graph[u][w]
				heapq.heappush(v, [dist[w], w])
	if dist[N - 1] == float('inf'):
		return -1
	return dist[N - 1]
print(main())


from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heapify
import sys, bisect, math, itertools
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7
mod2 = 998244353

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

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

def inpln(n):
	return list((int(sys.stdin.readline()) for i in range(n)))

def dijkstra_heap(s):
	d = [float('inf')] * n
	used = [True] * n
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heappush(edgelist, e)
	while len(edgelist):
		minedge = heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heappush(edgelist, [e[0] + d[v], e[1]])
	return d
(n, w) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(w):
	(x, y, z) = map(int, input().split())
	edge[x - 1].append([z, y - 1])
for i in range(n - 1):
	edge[i + 1].append([0, i])
res = dijkstra_heap(0)
if res[-1] == float('inf'):
	print(-1)
else:
	print(res[-1])


(N, M) = map(int, input().split(' '))
tree_list = [[] for _ in range(N)]
for _ in range(M):
	(L, R, C) = map(int, input().split(' '))
	tree_list[R - 1].append([C, L - 1])
inf = float('inf')
dp = [inf] * N
dp[N - 1] = 0
current_num = -1
flag = False
if len(tree_list[N - 1]) > 0:
	for i in reversed(range(N)):
		if dp[i] == inf:
			flag = True
			break
		current_start_paths = tree_list[i]
		if len(current_start_paths) > 0:
			current_start_paths.sort()
			for path in current_start_paths:
				if dp[path[1]] > dp[i] + path[0]:
					for j in range(path[1], i):
						if dp[i] + path[0] < dp[j]:
							dp[j] = dp[i] + path[0]
						else:
							break
	if dp[0] == inf or flag:
		print(-1)
	else:
		print(dp[0])
else:
	print(-1)


import heapq

def main():
	(n, m) = map(int, input().split())
	lrc = [list(map(int, input().split())) for _ in range(m)]
	adj = [[(0, i - 1)] for i in range(n)]
	adj[0] = []
	for (l, r, c) in lrc:
		l -= 1
		r -= 1
		adj[l].append((c, r))
	WHITE = 0
	GRAY = 1
	BLACK = 2

	def dijkstra(s):
		colors = [WHITE] * n
		ds = [float('inf')] * n
		ps = [-1] * n
		pq = []
		ds[s] = 0
		ps[s] = -1
		heapq.heappush(pq, (0, s))
		while pq:
			(d, u) = heapq.heappop(pq)
			colors[u] = BLACK
			if ds[u] < d:
				continue
			for (c, v) in adj[u]:
				if colors[v] != BLACK:
					if ds[u] + c < ds[v]:
						ds[v] = ds[u] + c
						ps[v] = u
						colors[v] = GRAY
						heapq.heappush(pq, (ds[v], v))
		return (ds, ps)
	(ds, ps) = dijkstra(0)
	ans = ds[-1]
	if ans == float('inf'):
		ans = -1
	print(ans)
main()


import sys
input = sys.stdin.readline
from heapq import *

def dijkstra():
	dist = [10 ** 18] * N
	dist[0] = 0
	pq = []
	heappush(pq, (0, 0))
	while pq:
		(d, v) = heappop(pq)
		if dist[v] < d:
			continue
		for (nv, w) in G[v]:
			if dist[nv] > dist[v] + w:
				dist[nv] = dist[v] + w
				heappush(pq, (dist[nv], nv))
	return dist
(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(1, N):
	G[i].append((i - 1, 0))
for _ in range(M):
	(L, R, C) = map(int, input().split())
	G[L - 1].append((R - 1, C))
ans = dijkstra()[-1]
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


import heapq
import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(N, M) = list(map(int, sys.stdin.readline().split()))
LRC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

def test():
	LRC.sort()
	dp = [INF] * N
	dp[0] = 0
	for (l, r, c) in LRC:
		l -= 1
		r -= 1
		for i in range(l, r + 1):
			dp[i] = min(dp[i], dp[l] + c)
	if dp[-1] == INF:
		print(-1)
	else:
		print(dp[-1])
heap = []
LRC.sort()
LRC = [(l - 1, r - 1, c) for (l, r, c) in LRC]
mi = 0
dp = [INF] * N
dp[0] = 0
for pos in range(N):
	if dp[pos] == INF:
		break
	while mi < M and LRC[mi][0] <= pos:
		(l, r, c) = LRC[mi]
		heapq.heappush(heap, (dp[pos] + c, r))
		mi += 1
	while heap and heap[0][1] <= pos:
		heapq.heappop(heap)
	if not heap:
		break
	dp[pos + 1] = heap[0][0]
if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


import heapq
(N, M) = map(int, input().split())
V = N
G = [[] for _ in range(V)]
s = 0
INF = float('inf')
for i in range(V - 1):
	G[i + 1].append([i, 0])
for _ in range(M):
	(l, r, c) = map(int, input().split())
	G[l - 1].append([r - 1, c])

def dijkstra(s):
	d = [INF for _ in range(V)]
	d[s] = 0
	que = []
	heapq.heappush(que, (0, s))
	while len(que) != 0:
		p = heapq.heappop(que)
		v = p[1]
		if d[v] < p[0]:
			continue
		for i in range(len(G[v])):
			e = G[v][i]
			if d[e[0]] > d[v] + e[1]:
				d[e[0]] = d[v] + e[1]
				heapq.heappush(que, (d[e[0]], e[0]))
	return d
L = dijkstra(s)
ans = -1 if L[N - 1] == INF else L[N - 1]
print(ans)


def update(k, x):
	k += N0 - 1
	data[k] = x
	while k >= 0:
		k = ~-k // 2
		data[k] = min(data[2 * k + 1], data[2 * k + 2])

def query(l, r):
	(L, R) = (l + N0, r + N0)
	s = INF
	while L < R:
		if R & 1:
			R -= 1
			s = min(s, data[R - 1])
		if L & 1:
			s = min(s, data[L - 1])
			L += 1
		L //= 2
		R //= 2
	return s
(n, m, *t) = map(int, open(0).read().split())
N0 = 2 ** n.bit_length()
INF = 10 ** 18
data = [INF] * 2 * N0
update(1, 0)
for (l, r, c) in sorted(zip(*[iter(t)] * 3)):
	update(r, min(data[r + N0 - 1], query(l, r) + c))
print(data[n + N0 - 1] % INF or -1)


from heapq import heappop, heappush, heapify

class Graph:

	def __init__(self, n, edge, indexed=1):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.deg = [0 for _ in range(n)]
		for e in edge:
			self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
			self.deg[e[1] - indexed] += 1

	def dijkstra(self, s, INF=10 ** 18, restore_to=None):
		dist = [INF for _ in range(self.n)]
		dist[s] = 0
		heap = [(0, s)]
		while heap:
			(cost, node) = heappop(heap)
			if dist[node] < cost:
				continue
			for (adj, adjcost) in self.graph[node]:
				if dist[node] + adjcost < dist[adj]:
					dist[adj] = dist[node] + adjcost
					heappush(heap, (dist[adj], adj))
		if restore_to is not None:
			g = restore_to
			if dist[g] == INF:
				return (dist, False)
			path = [g]
			node = g
			while node != s:
				node = prev[node]
				path.append(node)
			return (dist, path[::-1])
		return dist
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
E = list()
for _ in range(M):
	(l, r, c) = map(int, input().split())
	E.append((l - 1, r - 1, c))
for i in range(N - 1):
	E.append((i + 1, i, 0))
g = Graph(N, E, 0)
res = g.dijkstra(0)[N - 1]
print(res if res != 10 ** 18 else -1)


words = lambda t: list(map(t, input().split()))
(n, m) = words(int)
xs = []
for i in range(m):
	(a, b, c) = words(int)
	xs.append((b, a, c))
sxs = reversed(sorted(xs))
ans = [-1] * n
ans[-1] = 0
for (b, a, c) in sxs:
	if ans[b - 1] == -1:
		continue
	for i in range(a - 1, b - 1):
		if ans[i] != -1 and ans[i] <= ans[b - 1] + c:
			break
		ans[i] = ans[b - 1] + c
print(ans[0])


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
LRC = [tuple(map(int, input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for (l, r, c) in LRC:
	(l, r) = (l - 1, r - 1)
	es[l].append((r, c))
for i in range(1, N):
	es[i].append((i - 1, 0))
import heapq
hq = [(0, 0)]
INF = float('inf')
cost = [INF] * N
cost[0] = 0
while hq:
	(d, v) = heapq.heappop(hq)
	for (to, c) in es[v]:
		if cost[to] <= d + c:
			continue
		cost[to] = d + c
		heapq.heappush(hq, (d + c, to))
print(-1 if cost[-1] == INF else cost[-1])


import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10 ** 16

def dijkstra(s, VC):
	color = [WHITE for i in range(N)]
	d = [INFTY for i in range(N)]
	d[s] = 0
	pq = []
	heapq.heappush(pq, (0, s))
	while len(pq) != 0:
		u = heapq.heappop(pq)[1]
		color[u] = BLACK
		for (v, c) in VC[u]:
			if color[v] != BLACK:
				if d[u] + c < d[v]:
					d[v] = d[u] + c
					color[v] = GRAY
					heapq.heappush(pq, (d[v], v))
	return d
(N, M) = map(int, input().split())
V = [[] for i in range(N)]
for m in range(M):
	(L, R, C) = map(int, input().split())
	V[L - 1].append([R - 1, C])
	V[R - 1].append([L - 1, C])
for i in range(1, N):
	V[i].append([i - 1, 0])
d = dijkstra(0, V)
ans = d[N - 1]
if ans == INFTY:
	print(-1)
else:
	print(ans)


import sys
import heapq
(n, m) = map(int, input().split())
nextL = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	nextL[i].append([i - 1, 0])
INF = 10 ** 18
costs = [INF] * (n + 1)
costs[1] = 0
for i in range(m):
	(l, r, c) = map(int, sys.stdin.readline().split())
	nextL[l].append([r, c])
pc = []
heapq.heappush(pc, (0, 1))
unreach = set(range(1, n + 1))
while len(pc) > 0:
	(cost, target) = heapq.heappop(pc)
	if cost > costs[target]:
		continue
	for i in nextL[target]:
		nex = i[0]
		cos = i[1]
		if nex in unreach and cost + cos < costs[nex]:
			costs[nex] = cost + cos
			heapq.heappush(pc, (cost + cos, nex))
	unreach.remove(target)
if costs[n] == INF:
	print(-1)
else:
	print(costs[n])


import sys

def input():
	return sys.stdin.readline().strip()
(N, M) = list(map(int, input().split()))
LRC = []
for _ in range(M):
	LRC.append(tuple(map(int, input().split())))
LRC.sort()

class seg_tree:

	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.INF = 2 ** 100 - 1
		self.data = [self.INF] * (2 * self.N0)

	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k >= 0:
			k = (k - 1) // 2
			self.data[k] = min(self.data[2 * k + 1], self.data[2 * k + 2])

	def query(self, l, r):
		L = l + self.N0
		R = r + self.N0
		s = self.INF
		while L < R:
			if R & 1:
				R -= 1
				s = min(s, self.data[R - 1])
			if L & 1:
				s = min(s, self.data[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s
dist = seg_tree(N)
dist.update(0, 0)
for i in range(M):
	(L, R, C) = LRC[i]
	L -= 1
	R -= 1
	dist_start = dist.query(L, N)
	target_dist = dist.query(R, N)
	if dist_start + C < target_dist:
		dist.update(R, dist_start + C)
ans = dist.query(N - 1, N)
if ans == dist.INF:
	print(-1)
else:
	print(ans)


from operator import itemgetter
inf = float('inf')
(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
a.sort(key=itemgetter(2))
a.sort(key=itemgetter(1))
a.sort(key=itemgetter(0))
d = [inf] * (n + 1)
d[1] = 0
for i in range(m):
	(l, r, c) = a[i]
	if d[l] == inf:
		print(-1)
		exit()
	for j in range(r - l):
		if d[r - j] > d[l] + c:
			d[r - j] = d[l] + c
		else:
			break
print(d[n] if d[n] != inf else -1)


import sys
from heapq import heappop as hpp, heappush as hp
inf = 10 ** 20

def dijkstra(N, s, Edge):
	dist = [inf] * N
	Q = [(0, s)]
	decided = set()
	for _ in range(N):
		while True:
			(dn, vn) = hpp(Q)
			if vn not in decided:
				decided.add(vn)
				dist[vn] = dn
				break
		for (vf, df) in Edge[vn]:
			if vf not in decided:
				hp(Q, (dn + df, vf))
	return dist
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
Edge = [[] for _ in range(N)]
for i in range(M):
	(L, R, C) = map(int, readline().split())
	L -= 1
	R -= 1
	Edge[L].append((R, C))
for i in range(1, N):
	Edge[i].append((i - 1, 0))
for i in range(1, N):
	Edge[0].append((i, inf))
dist = dijkstra(N, 0, Edge)
if dist[N - 1] == inf:
	ans = -1
else:
	ans = dist[N - 1]
print(ans)


(n, m) = map(int, input().split())
d = []
for _ in range(m):
	(l, r, c) = map(int, input().split())
	d.append([l, r, c])
d.sort(key=lambda x: x[0])
g = [float('inf') for _ in range(n + 1)]
g[1] = 0
f = 1
for i in range(m):
	if d[i][0] > f:
		print(-1)
		exit()
	f = max(f, d[i][1])
	sm = d[i][2] + g[d[i][0]]
	if g[d[i][1]] > sm:
		g[d[i][1]] = sm
		j = d[i][1] - 1
		while g[j] > sm:
			g[j] = sm
			j -= 1
if g[n] != float('inf'):
	print(g[n])
else:
	print(-1)


import sys
from heapq import heapify, heappush, heappop
read = sys.stdin.read

def main():
	(N, M, *LRC) = map(int, read().split())
	graph = [[(0, i - 1)] for i in range(N + 1)]
	graph[1] = []
	for (L, R, C) in zip(*[iter(LRC)] * 3):
		graph[L].append((C, R))
	distance = [-1] * (N + 1)
	queue = []
	heapify(queue)
	heappush(queue, (0, 1))
	while queue:
		(cost, node) = heappop(queue)
		if distance[node] == -1:
			distance[node] = cost
			for (add_cost, next_node) in graph[node]:
				if distance[next_node] == -1:
					heappush(queue, (cost + add_cost, next_node))
	print(distance[-1])
main()


import sys
input = sys.stdin.readline

def main():
	(N, M) = map(int, input().split())
	E = []
	for _ in range(M):
		(l, r, c) = map(int, input().split())
		E.append((l - 1, r - 1, c))
	dp = [float('inf')] * N
	dp[0] = 0
	for (l, r, c) in sorted(E):
		for i in range(r, l, -1):
			if dp[i] > dp[l] + c:
				dp[i] = dp[l] + c
			else:
				break
	print(-1 if dp[-1] == float('inf') else dp[-1])
main()


(n, m) = map(int, input().split())
inf = 10 ** 18
pst = [[] for _ in range(n)]
for i in range(1, n):
	pst[i].append([0, i - 1])
for _ in range(m):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	pst[l].append([c, r])
import heapq
nxt = pst[0]
heapq.heapify(nxt)
seen = [inf for _ in range(n)]
seen[0] = 0
for x in nxt:
	seen[x[1]] = x[0]
while True:
	if nxt == []:
		print(-1)
		break
	(c, r) = heapq.heappop(nxt)
	if r == n - 1:
		print(seen[r])
		break
	for x in pst[r]:
		(xc, xr) = x
		if seen[xr] > seen[r] + xc:
			seen[xr] = seen[r] + xc
			heapq.heappush(nxt, [seen[xr], xr])


import sys
import heapq
input = sys.stdin.buffer.readline

def dijkstra(adj, start):
	dist = [float('inf')] * len(adj)
	dist[start] = 0
	q = []
	heapq.heappush(q, (0, start))
	while q:
		(min_dist, v_from) = heapq.heappop(q)
		if min_dist > dist[v_from]:
			continue
		v_tos = adj[v_from]
		for (v_to, cost) in v_tos:
			if min_dist + cost < dist[v_to]:
				dist[v_to] = min_dist + cost
				heapq.heappush(q, (dist[v_to], v_to))
	return dist
(N, M) = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
	(L, R, C) = map(int, input().split())
	adj[L].append((R, C))
for i in range(2, N + 1):
	adj[i].append((i - 1, 0))
dist = dijkstra(adj, 1)
if dist[N] < 10 ** 20:
	print(dist[N])
else:
	print(-1)


from heapq import heappush, heappop
(n, m) = map(int, input().split())
lrc = [list(map(int, input().split())) for i in range(m)]
data = [[] for i in range(n + 1)]
for i in range(2, n + 1):
	data[i].append([i - 1, 0])
for u in lrc:
	(l, r, c) = u
	data[l].append([r, c])
lst = []
flag = [-1] * (n + 1)
flag[1] = 0
for u in data[1]:
	heappush(lst, [u[1], u[0]])
while lst:
	(c, r) = heappop(lst)
	if r == n:
		print(c)
		break
	if flag[r] == -1:
		flag[r] = c
		for u in data[r]:
			if flag[u[0]] == -1:
				heappush(lst, [c + u[1], u[0]])
else:
	print(-1)


def main():
	import sys
	input = sys.stdin.readline
	INF = 10 ** 18
	(N, M) = map(int, input().split())
	G = [[] for _ in range(N + 1)]
	for _ in range(M):
		(L, R, C) = map(int, input().split())
		G[L].append([C, R])
		G[R].append([C, L])
	for i in range(1, N):
		G[i + 1].append([0, i])
	d = [INF] * (N + 1)

	def dijkstra(s):
		from heapq import heappop, heappush
		d[s] = 0
		pque = []
		heappush(pque, [0, s])
		while pque:
			p = heappop(pque)
			v = p[1]
			if d[v] < p[0]:
				continue
			for i in range(len(G[v])):
				e = G[v][i]
				if d[e[1]] > d[v] + e[0]:
					d[e[1]] = d[v] + e[0]
					heappush(pque, [d[e[1]], e[1]])
	dijkstra(1)
	print(-1 if d[-1] == INF else d[-1])
main()


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

def dijkstra(graph: list, node: int, start: int) -> list:
	INF = float('inf')
	dist = [INF] * node
	dist[start] = 0
	heap = [(0, start)]
	while heap:
		(cost, thisNode) = heappop(heap)
		for (NextCost, NextNode) in graph[thisNode]:
			dist_cand = dist[thisNode] + NextCost
			if dist_cand < dist[NextNode]:
				dist[NextNode] = dist_cand
				heappush(heap, (dist[NextNode], NextNode))
	return dist
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	edge[l].append((c, r))
for i in range(1, n):
	edge[i].append((0, i - 1))
dist = dijkstra(edge, n, 0)
ans = dist[-1] if dist[-1] != float('inf') else -1
print(ans)


import sys, heapq
input = sys.stdin.readline
(n, m) = map(int, input().split())
dg = 10 ** 6
edge = [[] for _ in [0] * n]
for _ in [0] * m:
	(l, r, c) = map(int, input().split())
	edge[l - 1].append(c * dg + r - 1)
d = [10 ** 20] * n
d[0] = 0
tank = []
for e in edge[0]:
	heapq.heappush(tank, e)
while len(tank) != 0:
	q = heapq.heappop(tank)
	go = q % dg
	if d[go] != 10 ** 20:
		continue
	cost = q // dg
	for i in range(go, -1, -1):
		if d[i] != 10 ** 20:
			break
		d[i] = cost
		for e in edge[i]:
			heapq.heappush(tank, e + cost * dg)
if d[-1] == 10 ** 20:
	print(-1)
else:
	print(d[-1])


import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1
(N, M) = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N - 1):
	edge[i + 1].append((0, i))
for _ in range(M):
	(l, r, c) = map(int, input().split())
	l -= 1
	r -= 1
	edge[l].append((c, r))
from heapq import heappop, heappush

def dijkstra(start, n, edges):
	d = [INF] * n
	used = [False] * n
	d[start] = 0
	used[start] = True
	edgelist = []
	for edge in edges[start]:
		heappush(edgelist, edge)
	while edgelist:
		minedge = heappop(edgelist)
		if used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = True
		for edge in edges[v]:
			if not used[edge[1]]:
				heappush(edgelist, (edge[0] + d[v], edge[1]))
	return d
d = dijkstra(0, N, edge)
print(d[-1] if d[-1] != INF else -1)


import sys
input = sys.stdin.readline
INF = 10 ** 18

def dijkstra(edges, size, src):
	from heapq import heappush, heappop
	dist = [INF] * size
	dist[src] = 0
	pq = [(0, src)]
	while pq:
		(d, v) = heappop(pq)
		if d > dist[v]:
			continue
		for (u, weight) in edges[v]:
			nd = d + weight
			if dist[u] > nd:
				dist[u] = nd
				heappush(pq, (nd, u))
	return dist
(N, M) = map(int, input().split())
G = [[] for _ in range(N + 1)]
for i in range(2, N + 1):
	G[i].append((i - 1, 0))
for _ in range(M):
	(L, R, C) = map(int, input().split())
	G[L].append((R, C))
dist = dijkstra(G, N + 1, 1)
print(dist[N] if dist[N] < INF else -1)


import heapq

def dijkstra(g: list, start, goal=None):
	num = len(g)
	dist = [float('inf') for i in range(num)]
	dist[start] = 0
	q = []
	heapq.heappush(q, (0, start))
	while q:
		(prov_cost, src) = heapq.heappop(q)
		if dist[src] < prov_cost:
			continue
		for (node, cost) in g[src]:
			if dist[node] > dist[src] + cost:
				dist[node] = dist[src] + cost
				heapq.heappush(q, (dist[node], node))
	return dist
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n - 1):
	g[i + 1].append((i, 0))
for i in range(m):
	(l, r, c) = map(int, input().split())
	g[l - 1].append((r - 1, c))
d = dijkstra(g, 0)
if d[n - 1] == float('inf'):
	print(-1)
else:
	print(d[n - 1])


(n, m) = map(int, input().split())
lrc = []
for _ in range(m):
	lrc.append(tuple(map(int, input().split())))
lrc.sort()
inf = 10 ** 15
dp = [inf] * (n + 1)
dp[1] = 0
for (l, r, c) in lrc:
	for i in range(r, l, -1):
		if dp[i] > dp[l] + c:
			dp[i] = dp[l] + c
		else:
			break
ans = -1 if dp[n] == inf else dp[n]
print(ans)


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

def dijkstra(start, ad):
	global dist
	N = len(ad)
	dist = [inf] * N
	dist[start] = 0
	pq = [(dist[start], start)]
	while pq:
		(dist_v, v) = heappop(pq)
		for (nv, nw) in ad[v]:
			if dist[nv] > dist_v + nw:
				dist[nv] = dist_v + nw
				heappush(pq, (dist[nv], nv))
(N, M) = map(int, input().split())
to = [[] for _ in range(N)]
for _ in range(M):
	(L, R, C) = map(int, input().split())
	L -= 1
	R -= 1
	to[L].append((R, C))
for i in range(1, N):
	to[i].append((i - 1, 0))
dijkstra(0, to)
ans = dist[N - 1]
if ans == inf:
	ans = -1
print(ans)


import sys
input = sys.stdin.readline
import heapq
(n, m) = map(int, input().split())
D = [0]
P = []
ans = float('inf')
for i in range(m):
	(l, r, c) = map(int, input().split())
	P.append((l, r, c))
P.sort(key=lambda x: x[0])
heapq.heappush(D, 0 * 10 ** 15 + 1)
for (l, r, c) in P:
	while D:
		ld = heapq.heappop(D)
		dd = ld // 10 ** 15
		ll = ld % 10 ** 15
		if ll < l:
			continue
		else:
			break
	if ll >= l:
		heapq.heappush(D, r + (dd + c) * 10 ** 15)
	heapq.heappush(D, ll + dd * 10 ** 15)
while D:
	ld = heapq.heappop(D)
	dd = ld // 10 ** 15
	ll = ld % 10 ** 15
	if ll == n:
		ans = min(ans, dd)
print(-1 if ans == float('inf') else ans)


import sys
from heapq import heappop, heappush

def dijkstra(s, t, links):
	q = [(0, s)]
	visited = set()
	while q:
		(cost, v) = heappop(q)
		if v in visited:
			continue
		if v == t:
			return cost
		visited.add(v)
		for (u, c) in links[v]:
			if u in visited:
				continue
			heappush(q, (cost + c, u))
	return -1
(n, m) = list(map(int, input().split()))
links = [set() for _ in range(n)]
for v in range(n - 1):
	links[v + 1].add((v, 0))
for line in sys.stdin:
	(l, r, c) = map(int, line.split())
	links[l - 1].add((r - 1, c))
print(dijkstra(0, n - 1, links))


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

class SegmentTree(object):

	def __init__(self, A, dot, e):
		n = 2 ** (len(A) - 1).bit_length()
		self.__n = n
		self.__dot = dot
		self.__e = e
		self.__node = [e] * (2 * n)
		for i in range(len(A)):
			self.__node[i + n] = A[i]
		for i in range(n - 1, -0, -1):
			self.__node[i] = dot(self.__node[2 * i], self.__node[2 * i + 1])

	def add(self, i, c):
		i += self.__n
		node = self.__node
		node[i] = self.__dot(c, node[i])
		while i != 1:
			i //= 2
			node[i] = self.__dot(node[2 * i], node[2 * i + 1])

	def sum(self, l, r):
		(vl, vr) = (self.__e, self.__e)
		l += self.__n
		r += self.__n
		while l < r:
			if l % 2 == 1:
				vl = self.__dot(vl, self.__node[l])
				l += 1
			l //= 2
			if r % 2 == 1:
				r -= 1
				vr = self.__dot(self.__node[r], vr)
			r //= 2
		return self.__dot(vl, vr)

def resolve():
	(n, m) = map(int, input().split())
	LRC = [0] * m
	for i in range(m):
		(l, r, c) = map(int, input().split())
		l -= 1
		LRC[i] = (l, r, c)
	LRC.sort()
	A = [INF] * n
	A[0] = 0
	tree = SegmentTree(A, min, INF)
	for (l, r, c) in LRC:
		s = tree.sum(l, r)
		tree.add(r - 1, s + c)
	ans = tree.sum(n - 1, n)
	if ans == INF:
		ans = -1
	print(ans)
resolve()


import heapq
import sys
input = sys.stdin.readline

def dijkstra_heap(s, N, edge):
	d = [float('inf')] * N
	used = [True] * N
	d[s] = 0
	used[s] = False
	edgelist = []
	for (a, b) in edge[s]:
		heapq.heappush(edgelist, a * 10 ** 6 + b)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge % 10 ** 6]:
			continue
		v = minedge % 10 ** 6
		d[v] = minedge // 10 ** 6
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, (e[0] + d[v]) * 10 ** 6 + e[1])
	return d

def main():
	(N, M) = map(int, input().split())
	edge = [[] for i in range(N)]
	for i in range(N - 1):
		edge[i + 1].append([0, i])
	for i in range(M):
		(L, R, C) = map(int, input().split())
		L -= 1
		R -= 1
		edge[L].append([C, R])
		edge[R].append([C, L])
	d = dijkstra_heap(0, N, edge)
	if d[N - 1] == float('inf'):
		print(-1)
	else:
		print(d[N - 1])
main()


import sys
from collections import defaultdict
from operator import itemgetter
from heapq import heappop, heappush

def inpl():
	return list(map(int, input().split()))
(N, M) = inpl()
D = [0] + [10 ** 18] * (N - 1)
g0 = itemgetter(0)
Q = sorted([inpl() for _ in range(M)], key=g0, reverse=True)
HQ = [(0, 0), (10 ** 18, N)]
for i in range(N):
	while HQ[0][1] < i:
		heappop(HQ)
	v = HQ[0][0]
	while len(Q) and i == Q[-1][0] - 1:
		(l, r, c) = Q.pop()
		heappush(HQ, (v + c, r - 1))
if v == 10 ** 18:
	print(-1)
else:
	print(v)


import sys
from heapq import heapify, heappop, heappush

def solve():
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	Edge = [[] for i in range(N)]
	for i in range(1, N):
		Edge[i].append((0, i - 1))
	for _ in range(M):
		(L, R, C) = map(int, input().split())
		Edge[L - 1].append((C, R - 1))
	Dist = [-1] * N
	Q = []
	heapify(Q)
	heappush(Q, (0, 0))
	while Q:
		(nowcost, nownode) = heappop(Q)
		if Dist[nownode] == -1:
			Dist[nownode] = nowcost
			for (addcost, nextnode) in Edge[nownode]:
				if Dist[nextnode] == -1:
					heappush(Q, (nowcost + addcost, nextnode))
	print(Dist[N - 1])
	return 0
solve()


import heapq
INF = 2 ** 62 - 1

def dijkstra(route_map, start_point):
	num_of_city = len(route_map)
	dist = [INF for _ in range(num_of_city)]
	dist[start_point] = 0
	heap_q = []
	heapq.heappush(heap_q, (0, start_point))
	while heap_q:
		(prev_cost, src) = heapq.heappop(heap_q)
		if dist[src] < prev_cost:
			continue
		for (dest, cost) in route_map[src].items():
			if dist[dest] > dist[src] + cost:
				dist[dest] = dist[src] + cost
				heapq.heappush(heap_q, (dist[dest], dest))
	return dist
(n, m) = list(map(int, input().split()))
route_map = [{} for _ in range(n)]
for i in range(m):
	(u, v, a) = list(map(int, input().split()))
	(u, v) = (u - 1, v - 1)
	if v in route_map[u].keys():
		a = min(a, route_map[u][v])
	route_map[u][v] = a
for i in range(n - 1):
	(u, v) = (i + 1, i)
	route_map[u][v] = 0
dijkstra_result = dijkstra(route_map, 0)
if dijkstra_result[-1] != INF:
	print(dijkstra_result[-1])
else:
	print(-1)


import sys
input = sys.stdin.readline
import heapq

def dijkstra(Route, v, start):
	Dist = [float('inf')] * v
	Dist[start] = 0
	Visited = [False] * v
	hq = [(0, start)]
	while hq:
		(dist, fr) = heapq.heappop(hq)
		Visited[fr] = True
		for (to, cost) in Route[fr]:
			if not Visited[to] and Dist[to] > dist + cost:
				Dist[to] = dist + cost
				heapq.heappush(hq, (Dist[to], to))
	return Dist

def main():
	(n, m) = map(int, input().split())
	Edges = [[] for _ in range(n)]
	for i in range(n - 1):
		Edges[i + 1].append((i, 0))
	for _ in range(m):
		(l, r, c) = map(int, input().split())
		l -= 1
		r -= 1
		Edges[l].append((r, c))
	Dist = dijkstra(Edges, n, 0)
	print(-1 if Dist[-1] == float('inf') else Dist[-1])
main()