Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M=map(int,input().split())
path=[[0 if i==j or i==max(j-1,0) else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

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(N):
      if dist[i]>d+path[ind][i]:
        dist[i]=d+path[ind][i]
        heapq.heappush(q,[dist[i],i])

if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])


Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
path=[[0 if i==j or i==max(j-1,0) else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

seen=[]
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if i not in seen and v==-1:
      v=i
    if i not in seen and dist[i]<dist[v]:
      v=i
  seen.append(v)
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])


Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M=map(int,input().split())
path=[[float("inf")]*N for i in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

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(N):
      if ind>=i:p=0
      else:p=path[ind][i]
      if dist[i]>d+p:
        dist[i]=d+p
        heapq.heappush(q,[dist[i],i])

if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M=map(int,input().split())
path=[[float("inf")]*N for i in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

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(N):
      if ind>=i:p=0
      else:p=path[ind][i]
      if dist[i]>d+p:
        dist[i]=d+p
        heapq.heappush(q,[dist[i],i])

if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

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(N):
      if dist[i]>d+path[ind][i]:
        dist[i]=d+path[ind][i]
        heapq.heappush(q,[dist[i],i])

if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

seen=[0]*N
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if seen[i]==0 and v==-1:
      v=i
    if seen[i]==0 and dist[i]<dist[v]:
      v=i
  seen[v]=1
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

seen=[]
dist=[float("inf")]*N
dist[0]=0
v=-1
while v!=N-1:
  v=-1
  for i in range(N):
    if i not in seen and v==-1:
      v=i
    if i not in seen and dist[i]<dist[v]:
      v=i
  seen.append(v)
  for i in range(N):
    dist[i]=min(dist[v]+path[v][i],dist[i])
    
if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

Fixed submission:
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])