Problem:
 Score : 600 points    Problem Statement 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.        Sample Input 1 4 3
1 3 2
2 4 3
1 4 6      Sample Output 1 5  We have an edge of length 2 between Vertex 1 and Vertex 2 , and an edge of length 3 between Vertex 2 and Vertex 4 , so there is a path of length 5 between Vertex 1 and Vertex 4 .       Sample Input 2 4 2
1 2 1
3 4 2      Sample Output 2 -1       Sample Input 3 10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3      Sample Output 3 28

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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])
    for u in range(1, n):
        to[u].append([u - 1, 0])
    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])
    print(-1)

main()

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

INF = 10**30

class Rmin():
	def __init__(self, size):
		
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = min(val, self.node[x])
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, m = map(int, input().split())
seg = []
for _ in range(m):
	l, r, c = map(int, input().split())
	seg.append([l-1, r-1, c])

seg.sort(reverse=True)
ans = [INF for _ in range(n)]
ans[0] = 0
tree = Rmin(n)

for i in range(1, n):
	while seg and seg[-1][0] == i-1:
		l, r, c = seg.pop()
		tree.Update(r, c + ans[l])
	ans[i] = tree.Get(i, n)

if ans[n-1] > 10**29:
	print(-1)
else:
	print(ans[n-1])

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
n,m,*t=map(int,open(0).read().split())
d=[0,0]+[1e18]*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**18or-1)

Solution (Python):
n,m,*t=map(int,open(0).read().split())
d=[0,0]+[1e18]*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**18or-1)

Solution (Python):
n,m,*t=map(int,open(0).read().split())
d=[0,0]+[1e18]*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]>1e17)or d[-2])

Solution (Python):
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]+[1e18]*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]>1e17)or d[-2])

Solution (Python):
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]+[1e18]*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]>1e17)or d[-2])

Solution (Python):


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])

Solution (Python):
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 = 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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
import sys
from heapq import heappop, heappush, heapify

def dijkstra(s, t, links):
    """Dijkstra algorism
    s: int, start node.
    t: int, target node.
    links: iterable, link infomation.
           links[i] contains edges from node i: (cost, target_node).

    return int, minimal cost from s node to t node.
    """
    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)
    

if __name__ == '__main__':
    print(main())

Solution (Python):
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)

Solution (Python):
N, M = map(int, input().split())
LRC = sorted([list(map(int, input().split())) for i in range(M)])

inf = float('inf')
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

if dp[-1] < inf:
    print(int(dp[-1]))
else:
    print(-1)

Solution (Python):
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)

Solution (Python):

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])

if __name__ == '__main__':
	main()

Solution (Python):
class SegmentTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size, initValue, cmpFunc):
        self.size = 1 << (size.bit_length())  
        self.data = [initValue] * (2 * self.size - 1)
        self.initValue = initValue
        self.cmpFunc = cmpFunc

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in rawData(self.size - 1)[:: -1]:
            self.data[i] = self.cmpFunc(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = self.cmpFunc(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = self.initValue
        while L < R:
            if R & 1:
                R -= 1
                ret = self.cmpFunc(ret, self.data[R - 1])
            if L & 1:
                ret = self.cmpFunc(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, M = map(int, input().split())
LRC = [tuple(map(int, input().split())) for _ in range(M)]
LRC.sort()

tree = SegmentTree(N, float('inf'), min)
tree.update(0, 0)

for l, r, c in LRC:
    l -= 1
    newDist = tree.query(l, r) + c
    if newDist < tree.query(r - 1, r):
        tree.update(r - 1, newDist)
ans = tree.query(N - 1, N)
print(-1 if ans == float('inf') else ans)

Solution (Python):
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])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


class SegmentTree:
    def __init__(self, n, ide_ele, op, init_val=[]):
        self.n = 2 ** (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.op = op
        self.seg = [ide_ele] * 2 * self.n
        if init_val:
            for i in range(n):
                self.seg[i + self.n - 1] = init_val[i]
            for i in range(self.n - 2, -1, -1):
                self.seg[i] = self.op(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, k, x):
        k += self.n - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.op(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, p, q):
        
        if q <= p:
            return self.ide_ele
        p += self.n - 1
        q += self.n - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
            p = p // 2
            q = (q - 2) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res

    def display(self):
        return self.seg[self.n - 1: -1]
    
    def query_point(self, p):
        return self.seg[p + self.n - 1]


n, m = LI()
lrc_list = sorted(LIR(m))
st = SegmentTree(n, INF, min)
st.update(0, 0)
for l, r, c in lrc_list:
    l_dist = st.query(l - 1, r)
    st.update(r - 1, min(st.query_point(r - 1), l_dist + c))
    

if st.query_point(n - 1) == INF:
    print(-1)
else:
    print(st.query_point(n - 1))

Solution (Python):
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in rawData(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

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

LRC = []
for _ in range(M):
    L, R, C = map(int, input().split())
    L -= 1
    LRC.append((L, R, C))
LRC.sort()

tree = MinSegTree(N)
tree.update(0, 0)
for l, r, c in LRC:
    newDist = tree.query(l, r) + c
    oldDist = tree.query(r - 1, r)
    if newDist < oldDist:
        tree.update(r - 1, newDist)

ans = tree.query(N - 1, N)
print(-1 if ans == INF else ans)

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

def set_heapq(que, edge, used, v, add_dist=0):
    '''
    確定地点vからつながる辺を全てqueに設定し、返却する

    Parameters
    que : heapque(touple or list)
        辺を管理するキュー (距離、次の行き先)のtopuleまたはlistにて管理
    edge : 2d list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    v : int
        グラフ上のノード ダイクストラでは確定したノードがvにあたる
    add_dist : int
        確定した地点に足し合わせる距離 スタート地点以外では何かしらの値が追加されることになる

    Returns
    que : heapque(touple or list)
        引数queにvからつながる辺を追加したキュー
    '''
    for a,b in edge[v]:
        if used[b]:
            heapq.heappush(que,(a+add_dist,b))
    return que

def dijkstra_heap(s, edge):
    '''
    ダイクストラ法でsで指定された地点からの全てのノードまでの最短距離を返却
    
    Parameters
    s : int
        スタート地点
    edge : 2d list
        全ての辺を格納する二次元のリスト
    
    Returns
    d : list
        スタート地点から全てのノードの最短距離のリスト
    '''
    d = [float("inf")] * n
    used = [True] * n 
    d[s], used[s] = 0, False
    edgelist = set_heapq([], edge, used, s)
    while len(edgelist):
        a, b = heapq.heappop(edgelist)
        
        if not used[b]:
            continue
        d[b], used[b] = a, False
        
        edgelist = set_heapq(edgelist, edge, used, b, d[b])
    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)

Solution (Python):
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()

Solution (Python):
import sys


class AlgSegmentTreeMin:
    def __init__(self, n, default_value):
        self.Nelem = n
        self.default_value = default_value
        self.size = 1 << (n.bit_length())
        self.data = [self.default_value] * (2 * self.size)

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i + i]
            y = self.data[i + i + 1]
            self.data[i] = min(x, y)
            i >>= 1

    def get_value(self, left, right):
        left += self.size
        right += self.size + 1
        x = self.default_value
        while left < right:
            if left & 1:
                y = self.data[left]
                x = min(x, y)
                left += 1
            if right & 1:
                right -= 1
                y = self.data[right]
                x = min(x, y)
            left >>= 1
            right >>= 1
        return x


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    stree = AlgSegmentTreeMin(n, 10 ** 15)
    lrc = [list(map(int, readline().split())) for _ in range(m)]
    lrc.sort()
    stree.update(0, 0)
    for l, r, c in lrc:
        l -= 1
        r -= 1
        now = stree.get_value(r, r)
        if now > c:
            tm = stree.get_value(l, r)
            if tm + c < now:
                stree.update(r, tm + c)
    mt = stree.get_value(n-1, n)
    print(mt if mt != stree.default_value else -1)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys


class AlgSegmentTreeMin:
    def __init__(self, n, default_value):
        self.Nelem = n
        self.default_value = default_value
        self.size = 1 << (n.bit_length())
        self.data = [self.default_value] * (2 * self.size)

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i + i]
            y = self.data[i + i + 1]
            self.data[i] = min(x, y)
            i >>= 1

    def get_value(self, left, right):
        left += self.size
        right += self.size + 1
        x = self.default_value
        while left < right:
            if left & 1:
                y = self.data[left]
                x = min(x, y)
                left += 1
            if right & 1:
                right -= 1
                y = self.data[right]
                x = min(x, y)
            left >>= 1
            right >>= 1
        return x


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    stree = AlgSegmentTreeMin(n, 10 ** 15)
    lrc = [list(map(int, readline().split())) for _ in range(m)]
    lrc.sort()
    stree.update(0, 0)
    for l, r, c in lrc:
        l -= 1
        r -= 1
        now = stree.get_value(r, r)
        if now > c:
            tm = stree.get_value(l, r)
            if tm + c < now:
                stree.update(r, tm + c)
    mt = stree.get_value(n-1, n)
    print(mt if mt != stree.default_value else -1)


if __name__ == '__main__':
    solve()

Solution (Python):
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)

Solution (Python):
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])


if __name__ == '__main__':
    main()