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



Sample input:
4 3
1 3 2
2 4 3
1 4 6


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
l.sort()

dp=[[float('inf')]*(n+1) for i in range(m+1)]
for i in range(m+1):
    dp[i][0]=0;dp[i][1]=0
for i in range(1,m+1):
    dp[i]=dp[i-1]
    for j in range(l[i-1][0],l[i-1][1]+1):
        dp[i][j]=min(dp[i][j],dp[i-1][l[i-1][0]]+l[i-1][2])
if dp[-1][-1]==float('inf'):
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
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_left

n, m = li()
lrc = [list(li()) for _ in range(m)]

# l -> r の降順にソート
lrc = sorted((sorted(lrc, key=lambda x: x[1])), 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_left(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])

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
dist = []
for i in range(m):
    l, r, c = map(int, sys.stdin.readline().split())
    dist.append([l, r, c])

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

res = [-1] * (n+1)
res[1] = 0
for i in dist:
    if res[i[0]] == -1:
        print(-1)
        exit()
    sh = res[i[0]] + i[2]
    if res[i[1]]!= -1 and  sh >= res[i[1]]:
        continue
    for j in range(i[0]+1, i[1]+1):
        if res[j] == -1 or res[j] > sh:
            res[j] = sh

print(res[n])

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(v) for v in input().split(' ')]

costs = []
for i in range(n):
    costs.append([0] * i)

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]

    for j in range(l, r):
        for k in range(j + 1, r + 1):
            c0 = costs[k - 1][j - 1]
            if c0 == 0 or c0 > c:
                costs[k - 1][j - 1] = c

import heapq
h = []
closed = 0

heapq.heappush(h, (0, n-1))

while len(h) > 0:
    c0, n1 = heapq.heappop(h)
    closed |= (1 << n1)

    if n1 == 0:
        print(c0)
        exit()

    for i in range(n):
        if i == n1:
            continue
        if closed & (1 << i) != 0:
            continue

        c1 = 0
        if i < n1:
            c1 = costs[n1][i]
        elif i > n1:
            c1 = costs[i][n1]
        if c1 > 0:
            heapq.heappush(h, (c0 + c1, i))

print("-1")

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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)
dist = [float('inf')]*(N+1)
dist[-1] = 0
for l, r, c in L:
    for d in range(l, r):
        dist[d] = min(dist[r]+c, dist[d])
if dist[1] == float('inf'):
    print(-1)
else:
    print(dist[1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().strip().split())
LRC = [list(map(int, input().strip().split())) for i in range(M)]
LRC.sort()
#print(LRC)

INF = -1
dp = [INF] * (N+1)
dp[1] = 0
for i in range(1,N+1):
    if dp[i] == -1:
        continue
    for lrc in LRC:
        if lrc[0] > i:
            break
        for  j in range(i+1, lrc[1]+1):
            if dp[j] == INF:
                dp[j] = dp[i] + lrc[2]
            else:
                dp[j] = min(dp[j], dp[i] + lrc[2])
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def dijkstra(s,n,w,cost):
  #始点sから各頂点への最短距離
  #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
  d=[inf] * n
  used=[False] * n
  d[s]=0
  
  while True:
    v=-1
    #まだ使われてない頂点の中から最小の距離のものを探す
    for i in range(n):
      if (not used[i]) and (v == -1):
        v = i
      elif (not used[i]) and d[i] < d[v]:
        v = i
    if v == -1:
      break
    used[v] = True
           
    for j in range(n):
      d[j] = min(d[j],d[v]+cost[v][j])
  return d

def main():
  n,m=LI()
  cost=[[inf for i in range(n)] for i in range(n)]

  for i in range(m):
    l,r,c=LI()
    for i in range(l-1,r-1):
      for j in range(i+1,r):
        cost[i][j]=min(cost[i][j],c)

  ans=dijkstra(0,n,m,cost)
  if ans[-1]==inf:
    return -1
  return ans[-1]

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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

DP = [float('INF')] * n
DP[0] = 0

for l, r, c in edges:
    for i in range(l+1, r+1):
        DP[i] = min(DP[i], DP[l]+c)

ans = DP[n-1]
if ans == float('INF'):
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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:
            i = (i-1)//2
            self.nodes[i] = min(self.nodes[2*i+1],self.nodes[2*i+2])

    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.n
        if r <= a or b <= l: return INF
        if a <= l and r <= b: return self.nodes[k]
        return min(self.query(a,b,2*k+1,l,(l+r)//2), self.query(a,b,2*k+2,(l+r)//2,r))

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)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class RangeSpannedGraph(object):
    def __init__(self, n, weighted = False):
        self.n = n
        self.N = N = 1 << (n - 1).bit_length()
        self._weighted = weighted
        N2, N3 = N * 2, N * 3
        ref, _add_edge = self._reflect, self._add_edge
        self.E = [[] for _ in range(N3)]
        for i in range(N - 1, 0, -1):
            cl, cr = i << 1, i << 1 | 1
            _add_edge(i, cl)
            _add_edge(i, cr)
            _add_edge(ref(cl + N2), i + N2)
            _add_edge(ref(cr + N2), i + N2)

    def _reflect(self, v):
        return v if v < 3 * self.N else v - 2 * self.N

    def add_edge(self, u, v, w = 0):
        self._add_edge(self.to_index(u), self.to_index(v), w)

    def _add_edge(self, u, v, w = 0):
        self.E[u].append((v, w)) if self._weighted else v

    def add_range_edge(self, l0, r0, l1, r1, w):
        N, E = self.N, self.E
        E.append([])
        v = len(E) - 1
        self._add_range_edge(l0 + N, r0 + N, v, w, to = True)
        self._add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(self, l, r, v, w, to):
        N2, E = self.N * 2, self.E
        ref, _add_edge = self._reflect, self._add_edge
        while l < r:
            if l & 1:
                _add_edge(ref(l + N2), v, w) if to else _add_edge(v, l, w)
                l += 1
            if r & 1:
                r -= 1
                _add_edge(ref(r + N2), v, w) if to else _add_edge(v, r, w)
            l >>= 1
            r >>= 1

    def to_index(self, v):
        return v + self.N

from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    rsg = RangeSpannedGraph(n, weighted = True)
    for _ in range(m):
        l, r, w = map(int, input().split())
        l -= 1
        rsg.add_range_edge(l, r, l, r, w)

    E = rsg.E
    dist = [INF] * len(E)
    dist[rsg.to_index(0)] = 0
    heap = [(0, rsg.to_index(0))]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[rsg.to_index(n - 1)]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class RangeSpannedGraph(object):
    def __init__(self, n, weighted = False):
        self.n = n
        self.N = N = 1 << (n - 1).bit_length()
        self._weighted = weighted
        N2, N3 = N * 2, N * 3
        ref, _add_edge = self._reflect, self._add_edge
        self.E = [[] for _ in range(N3)]
        for i in range(N - 1, 0, -1):
            cl, cr = i << 1, i << 1 | 1
            _add_edge(i, cl)
            _add_edge(i, cr)
            _add_edge(ref(cl + N2), i + N2)
            _add_edge(ref(cr + N2), i + N2)

    def _reflect(self, v):
        return v if v < 3 * self.N else v - 2 * self.N

    def add_edge(self, u, v, w = 0):
        self._add_edge(self.to_index(u), self.to_index(v ), w)

    def _add_edge(self, u, v, w = 0):
        self.E[u].append((v, w)) if self._weighted else v

    def add_range_edge(self, l0, r0, l1, r1, w):
        N, E = self.N, self.E
        E.append([])
        v = len(E) - 1
        self._add_range_edge(l0 + N, r0 + N, v, w, to = True)
        self._add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(self, l, r, v, w, to):
        N2, E = self.N * 2, self.E
        ref, _add_edge = self._reflect, self._add_edge
        while l < r:
            if l & 1:
                _add_edge(ref(l + N2), v, w) if to else _add_edge(v, l, w)
                l += 1
            if r & 1:
                r -= 1
                _add_edge(ref(r + N2), v, w) if to else _add_edge(v, r, w)
            l >>= 1
            r >>= 1

    def to_index(self, v):
        return v + self.N

from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    rsg = RangeSpannedGraph(n, weighted = True)
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        rsg.add_range_edge(u, v, u, v, w)

    # Dijkstra
    E = rsg.E
    dist = [INF] * len(E)
    dist[rsg.to_index(0)] = 0
    heap = [(0, rsg.to_index(0))]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[rsg.to_index(n - 1)]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class RangeSpannedGraph(object):
    def __init__(self, n, weighted = False):
        self.n = n
        self.N = N = 1 << (n - 1).bit_length()
        self._weighted = weighted
        N2, N3 = N * 2, N * 3
        ref, add_edge = self._reflect, self._add_edge
        E = [[] for _ in range(N3)]
        self.E = E
        for i in range(N - 1, 0, -1):
            cl, cr = i << 1, i << 1 | 1
            add_edge(i, cl)
            add_edge(i, cr)
            add_edge(ref(cl + N2), i + N2)
            add_edge(ref(cr + N2), i + N2)

    def _reflect(self, v):
        return v if v < 3 * self.N else v - 2 * self.N

    def _add_edge(self, u, v, w = 0):
        self.E[u].append((v, w)) if self._weighted else v

    def add_range_edge(self, l0, r0, l1, r1, w):
        N, E = self.N, self.E
        E.append([])
        v = len(E) - 1
        self._add_range_edge(l0 + N, r0 + N, v, w, to = True)
        self._add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(self, l, r, v, w, to):
        E, N2 = self.E, self.N * 2
        ref, add_edge = self._reflect, self._add_edge
        while l < r:
            if l & 1:
                add_edge(ref(l + N2), v, w) if to else add_edge(v, l, w)
                l += 1
            if r & 1:
                r -= 1
                add_edge(ref(r + N2), v, w) if to else add_edge(v, r, w)
            l >>= 1
            r >>= 1

    def to_index(self, v):
        return v + self.N

from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    rsg = RangeSpannedGraph(n, weighted = True)
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        rsg.add_range_edge(u, v, u, v, w)

    # Dijkstra
    E = rsg.E
    dist = [INF] * len(E)
    dist[rsg.to_index(0)] = 0
    heap = [(0, rsg.to_index(0))]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[rsg.to_index(n - 1)]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class RangeSpannedGraph(object):
    def __init__(self, n):
        self.n = n
        self.N = N = 1 << (n - 1).bit_length()
        N2, N3 = N * 2, N * 3
        ref = self._reflect
        E = [[] for _ in range(N3)]
        for i in range(N - 1, 0, -1):
            cl, cr = i << 1, i << 1 | 1
            E[i].append((cl, 0))
            E[i].append((cr, 0))
            E[ref(cl + N2)].append((ref(i + N2), 0))
            E[ref(cr + N2)].append((ref(i + N2), 0))
        self.E = E

    def _reflect(self, v):
        return v if v < 3 * self.N else v - 2 * self.N

    def add_range_edge(self, l0, r0, l1, r1, w):
        N, E = self.N, self.E
        E.append([])
        v = len(E) - 1
        self._add_range_edge(l0 + N, r0 + N, v, w, to = True)
        self._add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(self, l, r, v, w, to):
        E, ref, N2 = self.E, self._reflect, self.N * 2
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((v, w)) if to else E[v].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((v, w)) if to else E[v].append((r, 0))
            l >>= 1
            r >>= 1

    def to_index(self, v):
        return v + self.N

from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    rsg = RangeSpannedGraph(n)
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        rsg.add_range_edge(u, v, u, v, w)

    # Dijkstra
    E = rsg.E
    dist = [INF] * len(E)
    dist[rsg.to_index(0)] = 0
    heap = [(0, rsg.to_index(0))]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[rsg.to_index(n - 1)]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush

def build():
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

def add_range_edge(l0, r0, l1, r1, w):
    E.append([])
    v = len(E) - 1
    _add_range_edge(l0 + N, r0 + N, v, w, to = True)
    _add_range_edge(l1 + N, r1 + N, v, 0, to = False)

def _add_range_edge(l, r, v, w, to):
    while l < r:
        if l & 1:
            E[ref(l + N2)].append((v, w)) if to else E[v].append((l, w))
            l += 1
        if r & 1:
            r -= 1
            E[ref(r + N2)].append((v, w)) if to else E[v].append((r, w))
        l >>= 1
        r >>= 1

def resolve():
    global N, N2, E, ref
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, N3 = N * 2, N * 3
    E = [[] for _ in range(N3)]
    ref = lambda v : v if v < 3 * N else v - N2

    build()
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        add_range_edge(u, v, u, v, w)

    # Dijkstra (start : N, terminal : N + n - 1)
    dist = [INF] * (N3 + m)
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush

def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, N3 = N * 2, N * 3
    E = [[] for _ in range(N3)]
    ref = lambda v : v if v < 3 * N else v - N2

    # build range-edge graph
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    def add_range_edge(l0, r0, l1, r1, w):
        E.append([])
        v = len(E) - 1
        _add_range_edge(l0 + N, r0 + N, v, w, to = True)
        _add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(l, r, v, w, to):
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((v, w)) if to else E[v].append((l, w))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((v, w)) if to else E[v].append((r, w))
            l >>= 1
            r >>= 1

    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        add_range_edge(u, v, u, v, w)

    # Dijkstra (start : N, terminal : N + n - 1)
    dist = [INF] * (N3 + m)
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, N3 = N * 2, N * 3
    E = [[] for _ in range(N * 3 + m)]
    ref = lambda v : v if v < 3 * N else v - N2

    # build range-edge graph
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    # add range-edge
    for i in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        # lower
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((N3 + i, w))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((N3 + i, w))
            l >>= 1
            r >>= 1
        # upper
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[N3 + i].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[N3 + i].append((r, 0))
            l >>= 1
            r >>= 1

    # Dijkstra (source : N, termination : N + n - 1)
    dist = [INF] * (N3 + m)
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, now = N * 2, N * 3
    E = [[] for _ in range(N * 3 + m)]
    ref = lambda v : v if v < 3 * N else v - N2

    # build range-edge graph
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    # add range-edge
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        # lower
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((now, w))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((now, w))
            l >>= 1
            r >>= 1
        # upper
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[now].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[now].append((r, 0))
            l >>= 1
            r >>= 1
        now += 1

    # Dijkstra (source : N, termination : N + n - 1)
    dist = [INF] * now
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
  
N,M = IL()
data = ILL(M)
graph = [[] for i in range(N)]
for l,r,c in data:
  graph[l-1].append((c,r-1))
for i in range(1,N):
  graph[i].append((0,i-1))
  
def dijkstra(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  f = [False] * N
  q = [(0, start)]
  while q:
    c,u = heapq.heappop(q)
    if f[u]: continue
    d[u] = c
    f[u] = True
    for c,v in graph[u]:
      if not f[v]:
        heapq.heappush(q, (c + d[u], v))
  return d

ans = dijkstra(graph, 0)[-1]

if ans == INF:
  print(-1)
else:
  print(ans)