Problem:
 Score : 400 points    Problem Statement There is a directed graph with N vertices and M edges.
The i -th edge (1≤i≤M) points from vertex a_i to vertex b_i , and has a weight c_i .
We will play the following single-player game using this graph and a piece.  Initially, the piece is placed at vertex 1 , and the score of the player is set to 0 .
The player can move the piece as follows:   When the piece is placed at vertex a_i , move the piece along the i -th edge to vertex b_i . After this move, the score of the player is increased by c_i .   The player can end the game only when the piece is placed at vertex N .
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N .  When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf .      Constraints  2≤N≤1000   1≤M≤min(N(N-1),2000)   1≤a_i,b_i≤N (1≤i≤M)   a_i≠b_i (1≤i≤M)   a_i≠a_j or b_i≠b_j (1≤i<j≤M)   -10^9≤c_i≤10^9 (1≤i≤M)  c_i is an integer.  In the given graph, there exists a path from vertex 1 to vertex N .         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  c_1  a_2  b_2  c_2  :  a_M  b_M  c_M       Output Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf .        Sample Input 1 3 3
1 2 4
2 3 3
1 3 5      Sample Output 1 7  There are two ways to move the piece to vertex N=3 :   vertex 1 → vertex 2 → vertex 3 : score 4+3=7  vertex 1 → vertex 3 : score 5   Thus, the maximum possible score at the end of the game is 7 .       Sample Input 2 2 2
1 2 1
2 1 1      Sample Output 2 inf  It is possible to increase the score indefinitely by alternating between vertex 1 and 2 .       Sample Input 3 6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000      Sample Output 3 -5000000000

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
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
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)]
mod = 1000000007



n, m = LI()
G = [[] for _ in range(n)]
for a, b, c in LIR(m):
    G[a - 1] += [(b - 1, c)]


def bellman_ford(G, s=0):
    n = len(G)
    dist = [-INF] * n
    dist[s] = 0
    v_nows = {s}
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, c in G[u]:
                if dist[u] + c > dist[v]:
                    dist[v] = dist[u] + c
                    v_changeds.add(v)
        v_nows = v_changeds
    if not v_changeds:
        return dist[n - 1]
    if n - 1 in v_nows:
        return 'inf'
    for i in v_nows:
        dist[i] = INF
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        for v, c in G[u]:
            if v == n - 1:
                return 'inf'
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

Solution (Python):
def bellman_ford(n, edges, s, distance=None):
    if distance != None:
        d = distance[:]
    else :
        d = [float('inf')] * n
        d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True

        if not update or loop_cnt > n: break
    return d

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))

dist = bellman_ford(n, edges, 0)
test = bellman_ford(n, edges, 0, dist)

if dist[n-1] != test[n-1]:
    print("inf")
else :
    print(-dist[n-1])

Solution (Python):
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, -c))
    
    


def BellmanFord(E, N, source):
    
    
    
    
    inf = 10**20
    d = [inf for _ in range(N)]
    d[source] = 0
    
    
    for i in range(N):
        for j in range(N):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                if d[edge[0]] > d[j] + edge[1]:
                    d[edge[0]] = d[j] + edge[1]
                    if i == N-1 and edge[0] == N-1:
                        return -1
    
    return d

dist = BellmanFord(E, N, 0)
if dist == -1:
    print("inf")
else:
    print(-dist[N-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)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        E[a].append((b,-c))
        R[b].append((a,-c))

    from collections import deque
    state=[0]*n
    state[0]=1
    state[n-1]=2

    Q=deque([0])
    while(Q):
        v=Q.popleft()
        for nv,w in E[v]:
            if(state[nv]&1): continue
            state[nv]+=1
            Q.append(nv)

    Q=deque([n-1])
    while(Q):
        v=Q.popleft()
        for nv,w in R[v]:
            if(state[nv]&2): continue
            state[nv]+=2
            Q.append(nv)

    dist=[INF]*n
    dist[0]=0
    for k in range(n):
        for v in range(n):
            if(state[v]!=3): continue
            for nv,w in E[v]:
                if(state[nv]!=3): continue
                if(dist[nv]>dist[v]+w):
                    dist[nv]=dist[v]+w
                    if(k==n-1):
                        print("inf")
                        return
    print(-dist[-1])
resolve()

Solution (Python):
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]

inf=float("inf")
data=[-inf]*(n+1)
data[1]=0
for i in range(n):
    for a,b,c in abc:
        if data[a]!=inf:
            data[b]=max(data[b],data[a]+c)

lst=data[:]
for i in range(n):
    for a,b,c in abc:
        if data[a]!=inf:
            data[b]=max(data[b],data[a]+c)

que=[]
for i in range(1,n+1):
    if lst[i]!=data[i]:
        que.append(i)
        
flag=[0]*(n+1)
for u in que:
    flag[u]=1

li=[[] for i in range(n+1)]
for a,b,c in abc:
    li[a].append(b)

while que:
    h=que.pop()
    for u in li[h]:
        if flag[u]==0:
            flag[u]=1
            que.append(u)

if flag[n]==1:
    print("inf")
else:
    print(data[n])

Solution (Python):
INF = 10**18

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

graph = [[] for _ in range(N)]

for e in edge:
    graph[e[0]-1].append([e[1]-1,-e[2]])
    
dist = [INF for _ in range(N)]
dist[0] = 0

for _ in range(N):
    flag = False
    for node,g in enumerate(graph):
        for adj,cost in g:
            if dist[node] != INF and dist[node]+cost < dist[adj]:
                dist[adj] = dist[node]+cost
                if _==N-1:
                    update = adj
                flag = True
    if not flag:
        print(-dist[N-1])
        break
else:
    visited = [0 for _ in range(N)]
    visited[update] = 1
    stack = [update]
    while stack:
        node = stack.pop()
        for adj,c in graph[node]:
            if not visited[adj]:
                visited[adj] = 1
                stack.append(adj)
    if visited[N-1]:
        print('inf')
    else:
        print(-dist[N-1])

Solution (Python):
def bellman_ford(edges, num_v, start, end):
    """
    ベルマンフォード法
    :param edges: (from, to, cost)のリスト
    :param num_v: 頂点の数
    :param start: 始点
    :param end: 終点
    :return: 最小コスト
    """
    inf = float("inf")
    dist = [inf] * num_v
    dist[start - 1] = 0
    ans = -1

    for i in range(num_v):
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i == num_v - 1 and ans != dist[end - 1]:
                    return -1
        if i == num_v - 2:
            ans = dist[end - 1]

    return ans


def abc061_d():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        edges.append((a, b, -c))

    ans = bellman_ford(edges, n, 1, n)
    print(-ans if ans != -1 else "inf")


if __name__ == '__main__':
    abc061_d()

Solution (Python):
def abc061_d():
    n, m = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(m)]

    inf = float("inf")
    result = [inf] * n
    result[0] = 0

    for i in range(n - 1):
        for f, t, c in edges:
            result[t - 1] = min(result[t - 1], result[f - 1] - c)
    ans = result[n - 1]
    for f, t, c in edges:
        result[t - 1] = min(result[t - 1], result[f - 1] - c)
    print(-ans if ans == result[n - 1] else "inf")


if __name__ == '__main__':
    abc061_d()

Solution (Python):
(n,m),*l=[list(map(int,s.split()))for s in open(0)];d=[0]*2+[9e99]*n
for i in range(n*2):
 for a,b,c in l:d[b]=min(d[b],d[a]-c)
 if i==n:x=d[n]
print([-x,'inf'][d[n]!=x])

Solution (Python):
(n,m),*l=[list(map(int,s.split()))for s in open(0)];d=[0]*2+[9e99]*n
for i in range(n*2):
 for a,b,c in l:
  if d[b]>d[a]-c:d[b]=[d[a]-c,-9e99][i>n]
 if i==n:x=d[n]
print([-x,'inf'][d[n]!=x])

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
distance=[float('inf')]*n
distance[0]=0
for i in range(n-1):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
x=distance[n-1]
for i in range(n):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=-float('inf')
if distance[n-1]==x:
  print(-distance[n-1])
else:
  print('inf')

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
distance=[9999999999999999]*n
distance[0]=0
for i in range(n-1):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
f=[0]*n
for i in range(n):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
      f[l[j][1]-1]=1
    if f[l[j][0]-1]==1:
      f[l[j][1]-1]=1
if f[n-1]==0:
  print(-distance[n-1])
else:
  print('inf')

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

def bellman_ford(edges, n, s):
    d = [0] + [INF] * (n-1)
    for i in range(n):
        for f, t, c in edges:
            if d[f] == INF: continue
            if d[t] > d[f] + c:
                if i == n-1: d[t] = -INF
                else: d[t] = d[f] + c
    for i in range(n):
        for f, t, c in edges:
            if d[f] == INF: continue
            d[t] = min(d[t], d[f] + c)
    return d

n, m = map(int, input().split())
es = [None] * m
for i in range(m):
    f, t, c = map(int, input().split())
    es[i] = (f-1, t-1, -c)

d = bellman_ford(es, n, 0)
print(-d[n-1])

Solution (Python):
def bellmanford(num, start, goal, edges):
    cost = [float('inf')] * num
    cost[start] = 0
    for _ in range(num):
        updated = False
        for a, b, c in edges:
            if cost[b] > cost[a] + c:
                cost[b] = cost[a] + c
                updated = True
        if not updated: break
    else:
        return (-1,cost)
    return (1,-cost[goal])

def examD(inf):
    N, M = LI()
    v = []
    for i in range(M):
        x, y, z = map(int, input().split())
        v.append((x-1,y-1,-z))


    cur,d = bellmanford(N, 0, N-1, v)
    if cur==-1:
        inf_flag = [False]*N
        for i in range(N):
            for f, t, c in v:
                if d[f] == inf: continue
                if inf_flag[f] == True:
                    inf_flag[t] = True
                if d[t] > d[f] + c:
                    d[t] = d[f] + c
                    inf_flag[t] = True
        print("inf" if inf_flag[N-1] else -d[N-1])
    else:
        print(d)

import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD(inf)

Solution (Python):
n, m = map(int, input().split())
edges = [None] * m

for i in range(m):
    a, b, c = map(int, input().split())
    edges[i] = (a-1, b-1, -c)

INF = float("inf")
d = [INF] * n
d[0] = 0

for i in range(n-1):
    for f, t, c in edges:
        if d[f] == INF: continue
        d[t] = min(d[t], d[f] + c)

inf_flag = [False] * n

for i in range(n):
    for f, t, c in edges:
        if d[f] == INF: continue
        if inf_flag[f] == True:
            inf_flag[t] = True
        if d[t] > d[f] + c:
            d[t] = d[f] + c
            inf_flag[t] = True

print("inf" if inf_flag[n-1] else -d[n-1])

Solution (Python):

import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for _ in range(N+1) ]   
rev_al=[ [] for _ in range(N+1) ]   
edge=[] 
for _ in range(M):
    a,b,c=map(int, sys.stdin.readline().split())
    al[a].append(b)
    rev_al[b].append(a) 
    edge.append((a,b,c))


go=[0 for _ in range(N+1)]
back=[0 for _ in range(N+1)]


q=deque()
q.append(1) 
go[1]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if go[to]==0:
            go[to]=1
            q.append(to)



q=deque()
q.append(N) 
back[N]=1

while q:
    fro=q.popleft()
    for to in rev_al[fro]:
        if back[to]==0:
            back[to]=1
            q.append(to)


new_edge=[]     

for a,b,c in edge:
    if go[a]==1 and back[b]==1:
        new_edge.append((a,b,c))



dp=[ float("-inf") for _ in range(N+1) ]
dp[1]=0

for i in range(N):
    for fro,to,cost in new_edge:
        alt=dp[fro]+cost
        if dp[to]<alt:
            if i==N-1:
                print float("inf")
                quit()
            dp[to]=alt

print dp[N]

Solution (Python):

import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]   
rev_al=[ [] for _ in range(N+1) ]   
edge=[] 
for _ in range(M):
    a,b,c=map(int, sys.stdin.readline().split())
    al[a].append(b)
    rev_al[b].append(a) 
    edge.append((a,b,c))


go=[0 for _ in range(N+1)]
back=[0 for _ in range(N+1)]


q=deque()
q.append(1) 
go[1]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if go[to]==0:
            go[to]=1
            q.append(to)



q=deque()
q.append(N) 
back[N]=1

while q:
    fro=q.popleft()
    for to in rev_al[fro]:
        if back[to]==0:
            back[to]=1
            q.append(to)


new_edge=[]     

for a,b,c in edge:
    if go[a]==1 and back[b]==1:
        new_edge.append((a,b,c))



dp=[ float("-inf") for _ in range(N+1) ]
dp[1]=0

for i in range(N):
    for fro,to,cost in new_edge:
        alt=dp[fro]+cost
        if dp[to]<alt:
            if i==N-1:
                print float("inf")
                quit()
            dp[to]=alt

print dp[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 = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = LI()
    G[a - 1] += [(b - 1, c)]


def bellman_ford(G, start=0):
    n = len(G)
    costs = [-INF] * n
    costs[0] = 0
    v_nows = set([start])
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, c in G[u]:
                if costs[u] + c > costs[v]:
                    costs[v] = costs[u] + c
                    v_changeds.add(v)
        v_nows = v_changeds
    if not v_changeds:
        return costs[n - 1]

    for i in v_nows:
        costs[i] = INF
    que = deque(v_nows)
    while que:
        u = que.popleft()
        for v, _ in G[u]:
            if costs[v] != INF:
                costs[v] = INF
                que += [v]
    return costs[n - 1]


cost = bellman_ford(G, 0)
if cost == INF:
    print('inf')
else:
    print(cost)

Solution (Python):
n, m = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(m)]
d = [-float('inf')]*(n+1)
d[1] = 0
for _ in range(n):
    for i,j,c in e:
        d[j] = max(d[j], d[i]+c)
t = d[n]
for _ in range(n):
    for i,j,c in e:
        d[j] = max(d[j], d[i]+c)

if t < d[n]:
    print('inf')
else:
    print(d[n])

Solution (Python):
inf=10**43
n,m=map(int,input().split())
edges=[None]*m 
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1 
    b-=1 
    edges[i]=(a,b,-c)
d=[inf]*n 
f=1 
d[0]=0 
for i in range(n-1): 
    for (a,b,c) in edges: 
        if d[a]+c<d[b]:
            d[b]=d[a]+c 

for i in range(n):
    for (a,b,c) in edges: 
        if d[b]>d[a]+c:  
                         
            if b==n-1:
                f=0
                
            else:
                d[b]=d[a]+c 
if f:  
    print(-d[n-1])
else:
    print('inf')

Solution (Python):

N, M = map(int, input().split())
egdes = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 13
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
    for a, b, c in egdes:
        dist[b] = min(dist[b], dist[a] - c)
ans = dist[N]
for a, b, c in egdes:
    dist[b] = min(dist[b], dist[a] - c)
print(-ans if ans == dist[N] else 'inf')

Solution (Python):
import sys
N,M=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    edge.append([a-1,b-1,-c])
inf=10**30
dist=[inf]*N
dist[0]=0
for i in range(N+1):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            continue
        dist[y]=dist[x]+z
        if i==N and y==N-1:
            print('inf')
            sys.exit()
print(-dist[N-1])

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] 

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) 

def dijkstra(start, co):
    INF = 10 ** 15
    dist = [INF] * (N+1) 
    dist[start] = 0
    que = [(0, start, co)] 
    while que:
        score, place, count = heappop(que) 
        if score > dist[place]: 
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: 
                print('inf')
                exit()
            if dist[next_node] > score2 and count < 2000: 
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-d1[N])

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] 

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) 

def dijkstra(start, co):
    INF = 10 ** 15
    dist = [INF] * (N+1) 
    dist[start] = 0
    que = [(0, start, co)] 
    while que:
        score, place, count = heappop(que) 
        if score > dist[place] or count > 2000: 
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: 
                print('inf')
                exit()
            if dist[next_node] > score2 and count < 2000: 
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-d1[N])

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] 

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) 

def dijkstra(start, co):
    INF = float('inf')
    dist = [INF] * (N+1) 
    dist[start] = 0
    que = [(0, start, co)] 
    while que:
        score, place, count = heappop(que) 
        if score > dist[place] or count > 2000: 
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: 
                print('inf')
                exit()
            if dist[next_node] > score2 and count < 2000: 
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-int(d1[N]))

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] 

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) 
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) 
        if score < dist[place] or count > 2000: 
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: 
                print('inf')
                exit()
            if dist[next_node] < score2: 
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Solution (Python):
N, M = map(int, input().split())
edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))
edges.sort()

def bellmanford(n, edges, start):
    INF = float('inf')
    dist = [-INF] * (n+1) 
    dist[start] = 0

    for i in range(n):
        for (pre, ne, weight) in edges:
            if dist[pre] != -INF and dist[pre] + weight > dist[ne]:
                dist[ne] = dist[pre] + weight
                if i == n-1 and ne == n:
                    return 'inf'
    return dist[n]

answer = bellmanford(N, edges, 1)
print(answer)

Solution (Python):
n, m = map(int, input().split())
list_edge = []
for _ in range(m):
  a, b, c = map(int, input().split())
  list_edge.append((a-1, b-1, -c))

list_point = [float("inf") if i != 0 else 0 for i in range(n)]
for i in range(n+1):
  for a, b, c in list_edge:
    if list_point[a] != float("Inf") and list_point[b] > list_point[a] + c:
      list_point[b] = list_point[a] + c
      if i == n and b == n-1:
        print("inf")
        exit()
print(-1 * list_point[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] 

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) 
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) 
        if score < dist[place] or count > 2000: 
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: 
                print('inf')
                exit()
            if dist[next_node] < score2: 
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] 

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) 
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) 
        if score < dist[place] or count > 3000: 
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: 
                print('inf')
                exit()
            if dist[next_node] < score2: 
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Solution (Python):
import sys

INF = float('inf')

def Bellmanford(n, edges, r): 
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    
    return -d[n-1]
    

N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)

Solution (Python):


import sys
input=sys.stdin.readline  

def BELLMANFORD(point,n,d):
    cost       = [-float("inf")]*(n+1)
    preference = [None         ]*(n+1)      
    cost[point]= 0
    for i in range(n-1):                                  
        for nownode,nextnode,c in d:
            if cost[nextnode]<cost[nownode]+c:
                cost[nextnode]=cost[nownode]+c
                preference[nextnode]=nownode

    negative=[0]*(n+1)                                        
    
    for i in range(n):                  
        for nownode,nextnode,c in d:
            if negative[nownode]:
                negative[nextnode]=1
            if cost[nextnode]<cost[nownode]+c:
                cost[nextnode]=cost[nownode]+c
                preference[nextnode]=nownode
                negative[nownode]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    
    d=[tuple(map(int,input().split()))for i in [0]*m]
    
    x,y=(BELLMANFORD(1,n,d))
    
    if y[n]:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

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


def BELLMANFORD(point,n,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    for i in range(n-1):
        for (nownode,nextnode,c) in d:
            if cost[nextnode]>cost[nownode]+c:  
                cost[nextnode]=cost[nownode]+c
    for (nownode,nextnode,c) in d:
        if cost[nextnode]>cost[nownode]+c:
            if nextnode==n:
                return "inf"
            cost[nextnode]=cost[nownode]+c
            
    return -cost[n]


def main():
    n,m=map(int,input().split())
    
    d=[]
    for i in range(m):
        a,b,c=map(int,input().split())
        d.append((a,b,-c))
    
    print(BELLMANFORD(1,n,d))


if __name__ == '__main__':
    main()

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

def BELLMANFORD(point,d,n):
    cost       = [-float("inf")for node in range(n+1)]
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c

    negative=[0]*n                                        
    
    for i in range(n):                  
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    
    d={}
    for s in range(m):
        a,b,c=map(int,input().split())
        if a in d:
            d[a].append((b,c))
        else:
            d[a]=[(b,c)]
    
    x,y=(BELLMANFORD(1,d,n))
    
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

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

def BELLMANFORD(point,d,n):
    cost       = [-float("inf")for node in range(n+1)]
    preference = [None         for node in range(n+1)]      
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
 
    negative=[0]*n                                        
    
    for i in range(n):                  
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    
    d={}
    for s in range(m):
        a,b,c=map(int,input().split())
        if a in d:
            d[a].append((b,c))
        else:
            d[a]=[(b,c)]
    
    x,y=(BELLMANFORD(1,d,n))
    
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Solution (Python):
def bellman_ford(V, E, s, std):
  dist = [float('inf') for _ in range(V)]
  dist[s] = 0
  for i in range(V):
    for s, t, d in std:
      s -=1
      t -= 1
      d = -d
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d 
        if i == V-1 and t+1 == V:
          return -1 
  return dist

def main():
  N, M = map(int, input().split())
  abc = [list(map(int, input().split())) for _ in range(M)]
  dist = bellman_ford(N, M, 0, abc)
  if dist == -1:
    print('inf')
    exit()
  else:
    print(-dist[N-1])

if __name__ == "__main__":
  main()

Solution (Python):
n,m=map(int,input().split())
e=[list(map(int, input().split()))for _ in range(m)]
inf=float("inf")
d=[inf]*(n+1)
d[1]=0
for _ in range(n):
    for a,b,c in e:d[b]=min(d[b],d[a]-c)
x=d[n]
for a,b,c in e:d[b]=min(d[b],d[a]-c)
if x!=d[n]:print(inf)
else:print(-x)