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):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N,M = II()
L,R,C = Line(M,3)

from heapq import heappop, heappush
def dijkstra(E,s,n):
    inf=float('inf')
    d=[inf for _ in range(n)]
    d[s]=0
    q=[]
    heappush(q,(0,s))
    while q:
        du, u1 = heappop(q)
        if d[u1]<du: continue
        for v1,weight in E[u1].items():
            alt=du+weight
            if d[v1]>alt:
                d[v1]=alt
                heappush(q, (alt,v1))
    return d

A = []
for i in range(M):
    A.append((L[i]-1,R[i]-1,C[i]))
A.sort(key=lambda x:-x[2])

E = [dict() for _ in range(N)]
for i in range(M):
    E[A[i][0]][A[i][1]] = A[i][2]

for i in range(N-1):
    E[i+1][i] = 0

d = dijkstra(E,0,N)
if d[-1]==float('inf'):
    print(-1)
else:
    print(d[-1])

Solution (Python):


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)

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


N, C = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(C)]
L = sorted(L, key=lambda x: (x[1], -x[2], x[0]), reverse=True)

Seg = SegmentTree(N+1, func=lambda a, b: min(a, b))
Seg.set(N, 0)
Seg.build()

dist = [float("inf")]*(N+1)
dist[-1] = 0
for l, r, c in L:
    new = min(Seg.query(l, r+1)+c, Seg.query(l, l+1))
    Seg.update(l, new)
ans = Seg.query(1, 2)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        self.n = n
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        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):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        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

N,M = map(int,input().split())
edges = [list(map(int,input().split())) for i in range(M)]
edges.sort()

ST = SegTreeMin(N+1,10**15)
ST.update(0,0)

for i in range(M):
    min_ = ST.get_min(edges[i][0]-1,edges[i][1]-1)
    if min_+edges[i][2] < ST.get_min(edges[i][1]-1,edges[i][1]):
        ST.update(edges[i][1]-1,min_+edges[i][2])
if ST.get_min(N-1,N)!=10**15:
    print(ST.get_min(N-1,N))
else:print(-1)

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


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])
x=dijkstra_heap(0)[n-1]
if x==float("inf"):
  print(-1)
else:
  print(x)

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

Solution (Python):

"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

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

memo = sorted(tuple(map(int,input().split())) for _ in range(M))

seg = SegmentTree.all_identity(min, None, float('inf'), N)

seg[0] = 0

for l,r,c in memo:
    seg[r-1] = min(seg[r-1], seg[l-1:r] + c)

res = seg[N-1]
print(res if res != float('inf') else -1)

Solution (Python):

"""
Created on Sun Aug  4 22:01:34 2019

@author: miz18
"""




class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = min(x,self.node[k])
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res


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

road = []
for i in range(M):
    road.append(list(map(int,input().split())))

road.sort(key = lambda x: x[2])
road.sort(key = lambda x: x[0])

R = [10**27]*N
R[0] = 0
ST = SegmentTree(R,min,10**27)

for i in range(M):
    now_min = ST.get(road[i][0]-1,road[i][1]-1)
    ST.substitute(road[i][1]-1,now_min+road[i][2])
ans  = ST.get_one(N-1)

if ans>=10**27:
    print(-1)
else:
    print(ans)

Solution (Python):

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

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

mx = 10**15
ss = SegTree([0] + [mx] * n, n+1, mx, min)
for l, r, c in xs:
    mm = ss.query(l, n+1)
    nx = min(mm + c, ss.query(r, r+1))
    ss.update(r, nx)
r = ss.query(n-1,n)
print(r if r != mx else -1)

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class Graph:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.edges = [[] for _ in range(n_nodes)]

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


class Dijkstra:
    def __init__(self, graph):
        self.graph = graph

    def compute(self, s, t):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        while q:
            dist_x, x = heapq.heappop(q)
            if x == t:
                return distances, prev_nodes

            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes

    def compute_all(self, s):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        for t in range(self.graph.n_nodes):
            heapq.heappush(q, (distances[t], t))
        while q:
            dist_x, x = heapq.heappop(q)
            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes


n, m = ril()
graph = Graph(n)
for i in range(1, n):
    graph.add_edge(i, i - 1, 0)
for _ in range(m):
    a, b, c = ril()
    graph.add_edge(a - 1, b - 1, c)
dijkstra = Dijkstra(graph)
distances, _ = dijkstra.compute(0, n - 1)
d = distances[-1]
if d == float('inf'):
    print(-1)
else:
    print(d)

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

Solution (Python):
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: i番目をvalに変更する
    get_min: 区間[begin, end)の最小値を求める
    """
    def __init__(self, n):
        self.n = n
        self.INF = 10**18
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

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

    def get_min(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = min(s, self.node[end])
            if (begin - 1) & 1:
                s = min(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s


from operator import itemgetter


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

info = sorted(info, key = itemgetter(1))
st = SegmentTree(n)
st.update(0, 0)

i = 0
for num in range(n+1):
    while True:
        if i >= m:
            break
        if info[i][1] != num:
            break
        else:
            l = info[i][0] - 1
            r = num
            tmp = min(st.get_min(l, r) + info[i][2], st.get_min(num - 1, num))
            st.update(num-1, tmp)
            i += 1
ans = st.get_min(n-1, n)
if ans == 10**18:
    print(-1)
else:
    print(ans)

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

Solution (Python):



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

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

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

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

Solution (Python):

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


class Node:
    def __init__(self,value,index):
        self.value = value
        self.index = index

    def __str__(self):
        return 'val : ' + str(self.value) + ' index : ' + str(self.index)


class SegmentTree:
    def __init__(self,N,default_list,default_value=INF):
        self.N0 = pow(2,(N-1).bit_length())
        self.nodes = [Node(default_value,i+1-self.N0) for i in range(2*self.N0-1)]
        for i in reversed(range(2*self.N0-1)):
            ind = i+1-self.N0
            if ind >= N:
                self.nodes[i].value = default_value
            elif N > ind >= 0:
                self.nodes[i].value = default_list[ind]
            else:
                self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2])

    def __getitem__(self,key): 
        return self.nodes[key+self.N0-1].value

    def __setitem__(self,i,x): 
        i += self.N0 - 1
        self.nodes[i].value = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2])

    def __str__(self):
        return '['+', '.join(map(str,[self.nodes[i+self.N0-1].value for i in range(self.N0)]))+']'

    def query(self,L,R): 
        retnode = Node(INF,INF)
        L += self.N0
        R += self.N0
        while L < R:
            if R&1 :
                R -= 1
                retnode = self.process(retnode,self.nodes[R-1])
            if L&1 :
                retnode = self.process(retnode,self.nodes[L-1])
                L += 1
            L >>= 1; R >>= 1
        return retnode

    def process(self,node_x,node_y): 
        if node_x.value < node_y.value:
            return node_x
        else:
            return node_y


N,M = inpl()

ST = SegmentTree(N,[INF]*N)
ST[0] = 0

LRc = []
for _ in range(M):
    L,R,c = inpl()
    LRc.append((L-1,R-1,c))

LRc.sort()

for L,R,c in LRc:
    MIN = ST.query(L,R+1).value
    if ST[R] > MIN + c:
        ST[R] = MIN + c

if ST[N-1] == INF:
    print(-1)
else:
    print(ST[N-1])

Solution (Python):
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])
if __name__ == "__main__":
    main()

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

Solution (Python):
import sys
input = sys.stdin.readline

INF = 10**18

class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [INF] * (2*self.size-1)
        self.initialize(a)

    
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data[i] = min(self.data[i*2 + 1], self.data[i*2 + 2])

    
    def update(self, k, x):
        k += self.size - 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.size; R = r + self.size
        s = 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

n, m = [int(item) for item in input().split()]
dist = [INF] * n
dist[0] = 0
rmq = RMQ(dist)
lrc = []
for i in range(m):
    l, r, c = [int(item) for item in input().split()]
    l -= 1; r -= 1
    lrc.append((l, r, c))
lrc.sort()

for l, r, c in lrc:
    min_dist = rmq.query(l, r+1)
    r_dist = rmq.query(r, r+1)
    if min_dist + c < r_dist:
        rmq.update(r, min_dist+c)

ans = rmq.query(n-1, n)
if ans == INF:
    print(-1)
else:
    print(ans)