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 deque
from sys import stdin
def input():
    return stdin.readline().strip()

inf = float('inf')

n, m = map(int, input().split())

edge = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(m):
    i, j, k = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    weight[i].append(k)

seen = [-inf] * n
todo = deque([(0, 0, 1)])
while len(todo) > 0:
    node, score, num = todo.popleft()
    if num > 2 * n:
        break

    for i in range(len(edge[node])):
        if seen[edge[node][i]] < score + weight[node][i]:
            seen[edge[node][i]] = score + weight[node][i]
            todo.append((edge[node][i], score + weight[node][i], num + 1))
            if edge[node][i] == n - 1 and num >= n:
                print('inf')
                exit()

print(seen[n-1])

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

cost = [-float("INF")]*(N+1)
cost[1] = 0
cnt = 0
flag = True
for _ in range(N):
    for a,b,c in edges:
        if cost[a]+c > cost[b]:
            cost[b] = cost[a]+c

tmp = cost[N]

for _ in range(N):
    for a,b,c in edges:
        if cost[a]+c > cost[b]:
            cost[b] = cost[a]+c

if tmp < cost[N]:
    print("inf")
else:
    print(tmp)

Solution (Python):
INF = 10**30
import sys
sys.setrecursionlimit(10**6)
def bellman_ford(s, t, g):
    d = [INF for _ in range(n)] 
    d[s] = 0 
    val_at_t = INF 
    for i in range(n):
        
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                
        
        if i == n-1 and val_at_t > d[t]:
            return []
        val_at_t = d[t] 
    return d

n, m = map(int, input().split()) 
g = []
for _ in range(m):
    x, y, z = map(int, input().split()) 
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])
    
ans = bellman_ford(0, n-1, g)

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

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m = map(int,ipt().split())

    way = [[] for i in range(n+1)]
    gway = [[] for i in range(n+1)]
    rway = [[] for i in range(n+1)]
    for i in range(m):
        a,b,c = map(int,ipt().split())
        way[a].append((b,-c))
        rway[b].append(a)
        gway[a].append(b)

    ar = [True]*(n+1)
    ar[n] = False
    q = [n]
    while q:
        qi = q.pop()
        for j in rway[qi]:
            if ar[j]:
                ar[j] = False
                q.append(j)
    q = [1]
    ar2 = [True]*(n+1)
    ar2[1] = False
    while q:
        qi = q.pop()
        for j in gway[qi]:
            if ar2[j]:
                ar2[j] = False
                q.append(j)

    for i in range(1,n+1):
        if ar[i] or ar2[i]:
            way[i] = []

    def bellmanford(s,g,way):
        n = len(way)
        d = [10**18]*(n)
        d[s] = 0
        sl = 0
        re = True
        while re:
            re = False
            for i in range(1,n):
                for j,cj in way[i]:
                    if d[j] > d[i]+cj:
                         d[j] = d[i]+cj
                         re = True
            sl += 1
            if sl == n:
                d[g] = -10**18
                break
        return d[g]

    ans = bellmanford(1,n,way)
    if ans == -10**18:
        print("inf")
    else:
        print(-ans)

    return None

if __name__ == '__main__':
    main()

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

def bellmanFord(G,s):
  D=[INF for i in range(n)]
  D[s]=0
  for i in range(1,n):
    for x,y,z in G:
      D[y]=min(D[y],D[x]+z)
  ans=-D[n-1]
  for x,y,z in G:
    D[y]=min(D[y],D[x]+z)
  if ans!=-D[n-1]:
    return -1
  else:
    return -D[n-1]

ans=bellmanFord(G,0)
if ans==-1:
  print('inf')
else:
  print(ans)

Solution (Python):
n,m=map(int,input().split())
INF=float('inf')
G=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  G.append([a-1,b-1,-c])
  
def main():
  D=[INF for _ in range(n)]
  D[0]=0
  for i in range(n):
    for x,y,z in G:
      if D[x]!=INF and D[y]>D[x]+z:
        D[y]=D[x]+z
        if i==n-1 and y==n-1:
          return 'inf'
  return -D[n-1]
   
if __name__=='__main__':
  print(main())

Solution (Python):
N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
dp = (N+1)*[float("inf")]
dp[1] = 0

for n in range(N):
  for a,b,c in E:
    dp[b] = min(dp[b],dp[a]-c)

x = dp[N]

for a,b,c in E:
  dp[b] = min(dp[b],dp[a]-c)

if x!=dp[N]:
  print("inf")
else:
  print(-x)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict
N,M = map(int,input().split())
abc = [list(map(int,input().split())) for i in range(M)]

g = defaultdict(list)
rg = defaultdict(list)
for a,b,c in abc:
    g[a].append((b,c))
    rg[b].append(a)

inf = 10**20
score = [-inf]*(N+1)
score[1] = 0

for i in range(N-1):
    for v in range(1,N+1):
        for nv, c in g[v]:
            if score[v] + c > score[nv]:
                score[nv] = score[v] + c

update = [False]*(N+1)
for v in range(1,N+1):
    for nv, c in g[v]:
        if score[v] + c > score[nv]:
            score[nv] = score[v] + c
            update[v] = True

visited = [False]*(N+1)
l = [N]
while l:
    v = l.pop()
    visited[v] = True
    for nv in rg[v]:
        if not visited[nv]:
            l.append(nv)
for u,v in zip(update, visited):
    if u and v:
        print('inf')
        exit()

print(score[N])

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
e = []
for _ in range(M):
  u, v, c = map(int, input().split())
  e.append((u, v, -c))
inf = 10 ** 18
d = [inf] * (N + 1)
d[1] = 0
for _ in range(N - 1):
  for u, v, c in e: d[v] = min(d[v], d[u] + c)
loop = []
for u, v, c in e:
  if d[v] > d[u] + c:
    d[v] = min(d[v], d[u] + c)
    loop.append(v)
if len(loop) == 0:
  print(-d[-1])
  exit(0)
for v in loop: d[v] = -inf
for _ in range(N - 1):
  for u, v, c in e:
    if v == N and (d[v] > d[u] + c): break
    d[v] = min(d[v], d[u] + c)
  else: continue
  break
else: 
  print(-d[-1])
  exit(0)
print("inf")

Solution (Python):
N, M = map(int, input().split())
edges = [None]*M
INF = 10**18

for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a-1, b-1, -c)
    
def bellman(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[-1]
    
ans = bellman(N, edges, 0)
print(ans)

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):
    dist = [-INF] * n
    dist[s] = 0
    v_nows = {s}
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, ci in G[u]:
                if dist[u] + ci > dist[v]:
                    dist[v] = dist[u] + ci
                    v_changeds.add(v)
        v_nows = v_changeds
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        for v, _ in G[u]:
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

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
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        for v, c in G[u]:
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

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]
    for i in v_nows:
        dist[i] = INF
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        for v, c in G[u]:
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

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]
    for i in v_nows:
        dist[i] = INF
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        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):
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N, M = map(int, input().split())
    edges = []  
    repn = [[] for _ in range(N)]
    reverse_repn = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        edges.append((a, b, c))
        repn[a].append(b)
        reverse_repn[b].append(a)
    """
    辺の重みを正負逆転させることで単一始点最短経路問題を解けば良い。
    ベルマンフォードで負閉路を検出したら"inf"を返す。
    ABC137Eを参考にする。
    これも負閉路が1~(N-1)のパス上にあることの確認が必要ですね。。。
    """
    reachable_from_1 = [0] * N
    reachable_from_N = [0] * N
    ok = [0] * N

    def dfs(v):
        if reachable_from_1[v]: return
        reachable_from_1[v] = 1
        for u in repn[v]: dfs(u)

    def reverse_dfs(v):
        if reachable_from_N[v]: return
        reachable_from_N[v] = 1
        for u in reverse_repn[v]: reverse_dfs(u)

    dfs(0)
    reverse_dfs(N - 1)
    for i in range(N):
        if reachable_from_1[i] and reachable_from_N[i]: ok[i] = 1

    
    d = [10**18] * N
    d[0] = 0
    step = 0
    update = True
    while update:
        update = False
        for a, b, c in edges:
            if not ok[a]: continue
            if not ok[b]: continue
            new_cost = d[a] - c
            if new_cost < d[b]:
                update = True
                d[b] = new_cost
        step += 1
        if step > N:
            print("inf")
            return
    print(-d[N - 1])


if __name__ == "__main__":
    main()

Solution (Python):
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    dist = [float('inf')] * v
    dist[s] = 0
    neg = [False] * v

    for i in range(v-1):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
    
    for i in range(v):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
                neg[q] = True
            if neg[p]:
                neg[q] = True

    if neg[v-1]:
        return False
    else:
        return -dist[v-1]


v, e = map(int, input().split())

edge = []
for _ in range(e):
    s, t, d = map(int, input().split())
    edge.append([s-1, t-1, -d])

res = bellman_ford(0)

if not res:
    print('inf')
else:
    print(res)

Solution (Python):
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    dist = [float('inf')] * v
    dist[s] = 0
    neg = [False] * v

    for i in range(v):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
    
    for i in range(v):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
                neg[q] = True
            if neg[p]:
                neg[q] = True

    if neg[v-1]:
        return False
    else:
        return -dist[v-1]


v, e = map(int, input().split())

edge = []
for _ in range(e):
    s, t, d = map(int, input().split())
    edge.append([s-1, t-1, -d])

res = bellman_ford(0)

if not res:
    print('inf')
else:
    print(res)

Solution (Python):
n,m = map(int, input().split())
from collections import defaultdict
G = defaultdict(dict)
for i in range(1,n):
    G[i+1] = {}
for i in range(m):
    a,b,c = map(int, input().split())
    G[a][b] = c
start_vertex = 1
def bellmanford(G, start_vertex):
    if start_vertex not in G:
        return -1, -1
    distances = {}
    parents   = {}
    for node in G:
        distances[node] = float('-inf')
        parents[node]   = None
    distances[start_vertex] = 0
    for _ in range(len(G)-1):
        for node in G.keys():
            for neighbor in G[node]:
                if distances[neighbor] < distances[node] + G[node][neighbor]:
                    distances[neighbor] = distances[node] + G[node][neighbor]
                    parents[neighbor]   = node
    pathnode = n
    while pathnode != start_vertex:
        for neighbor in G[pathnode]:
            if distances[neighbor] < distances[pathnode] + G[pathnode][neighbor]:
                print('inf' , flush=True)
                return -1,-1
        pathnode = parents[pathnode]
    return distances, parents
distances, parents = bellmanford(G, start_vertex)
if distances != -1:
    print(distances[n] , flush=True)

Solution (Python):
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * m
INF = float('inf')
dist = [INF] * n
dist[0] = 0
for i in range(m):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    c[i] *= -1
for loop in range(n - 1):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[n - 1]

neg = [False] * n
for loop in range(n):
    for i in range(m):
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            neg[b[i]] = True
        if neg[a[i]]:
            neg[b[i]] = True
if neg[n - 1]:
    print('inf')
else:
    print(-ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, M = getNM()
edges = []
for i in range(M):
    a, b, c = getNM()
    edges.append([a - 1, b - 1, c])

def bellman(edges, num_v):
    dist = [-float('inf') for i in range(num_v)]
    dist[0] = 0

    
    for i in range(N - 1):
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    
    nega = [0] * N
    for i in range(N):
        for edge in edges:
            
            if nega[edge[0]] == 1:
                nega[edge[1]] = 1
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                nega[edge[1]] = 1

    if nega[N - 1]:
        print('inf')
        exit()

    return dist

print(bellman(edges, N)[N - 1])

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

def bellmanford(n,e,r):
  costs = [INF]*n
  costs[r] = 0
  for i in range(n):
    for u,v,c in e:
      if costs[u]+c > costs[v] and costs[u]!=INF:
        costs[v] = costs[u]+c
        if i==n-1 and v==n-1:
          return 'inf'
  return costs[n-1]

n,m = map(int, input().split())
edge = []
for i in range(m):
  a,b,t = map(int, input().split())
  edge.append((a-1,b-1,t))

print(bellmanford(n,edge,0))

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

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

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

INF = 10 ** 40
S = [-INF] * N
S[0] = 0

def score(fst, s, C):
    for nx, p in R[fst]:
        if S[nx] >= s + p or S[nx] >= INF:
            continue
        S[nx] = s + p
        if nx in C:
            S[nx] = INF
        C[nx] = C.get(nx, 0) + 1
        score(nx, S[nx], C)
        C[nx] -= 1
        if C[nx] == 0:
            del C[nx]

score(0, 0, {0: 1})

if S[-1] < INF:
    ans = S[-1]
else:
    ans = "inf"

print(ans)

Solution (Python):
N,M = map(int,input().split())
dp = [-float("INF")]*(N+1)
dp[1] = 0
edges = [list(map(int,input().split())) for _ in range(M)]
cnt = 0
while cnt < N:
    cnt += 1
    for a,b,c in edges:
        dp[b] = max(dp[a]+c,dp[b])
tmp = dp[N]
cnt = 0
while cnt < N:
    cnt += 1
    for a,b,c in edges:
        dp[b] = max(dp[a]+c,dp[b])
if dp[N] > tmp:
    print("inf")
else:
    print(dp[N])

Solution (Python):
def Bellmanford(n,edges,r):
    d = [float('inf')]*n
    d[r] = 0
    for i in range(n):
        for u,v,c in edges:
            if d[u] != float('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,input().split())
edges = [None]*m
for i in range(m):
    a,b,c = map(int,input().split())
    edges[i] = (a-1,b-1,-c)
ans = Bellmanford(n,edges,0)
print(ans)

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

def main():
    n,m=map(int,rl().strip().split())
    eaw=[list(map(int,rl().strip().split())) for _ in range(m)]
    d=dict(((x[0]-1,x[1]-1),-x[2]) for x in eaw)
    inf=10**14
    mdl=[inf]*n
    mdl[0]=0
    def blrelax(dl,k):
        for _ in range(k):
            for e in iter(d):
                if dl[e[0]]+d[e]<dl[e[1]]:
                    dl[e[1]]=dl[e[0]]+d[e]
    blrelax(mdl,n-1)
    a1=mdl[n-1]
    blrelax(mdl,n)
    a2=mdl[n-1]
    if a1>a2:
        print('inf')
    else:
        print(-a1)
    
if __name__=='__main__':
    main()

Solution (Python):
from collections import deque
def belman(s,n,w,es):
    d = [-float("inf")] * n 
    d[s] = 0
    c = 0
    while True:
      update = False
      for p,q,r in es:
        if d[p] != -float("inf") and d[q] < d[p] + r:
          d[q] = d[p] + r
          update = True
          c += 1
        if c > w:
          return 'inf'
      if not update:
        break
    return d[n-1]

def use_path(n,start,es):
    q = deque()
    chk = [False] * n
    q.append(start)
    chk[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for nex in es[node]:
            if not chk[nex]:
                chk[nex] = True
                q.append(nex)
                used.add(nex)
    return used

n,w = map(int,input().split())
es = []
l = [[] for i in range(n)]
r = [[] for i in range(n)]

for i in range(w):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    r[b].append(a)
    es.append((a,b,c))

use = use_path(n,0,l) & use_path(n,n-1,r)
ess = [(a,b,c) for a,b,c in es if a in use and b in use]
print(belman(0,n,w*2,ess))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, M = getNM()
edges = []
for i in range(M):
    a, b, c = getNM()
    edges.append([a - 1, b - 1, c])

def bellman(edges, num_v):
    dist = [-float('inf') for i in range(num_v)]
    dist[0] = 0

    
    for i in range(N - 1):
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    
    nega = [0] * N
    for i in range(N):
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                nega[edge[1]] = 1

    if nega[N - 1]:
        print('inf')
        exit()

    return dist

print(bellman(edges, N)[N - 1])

Solution (Python):
from scipy.sparse.csgraph import connected_components, bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix

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


connect_check = csr_matrix(([1] * (M + 1), (frm + [N - 1], to + [0])), shape=(N, N))
_, labels = connected_components(connect_check, connection='strong')
label_num = labels[0]
frm_c, to_c, length_c = [], [], []
for i in range(M):
    if labels[frm[i]] == labels[to[i]] == label_num:
        frm_c.append(frm[i])
        to_c.append(to[i])
        length_c.append(length[i])

matr = csr_matrix((length_c, (frm_c, to_c)), shape=(N, N))

try:
    ans = -int(bellman_ford(matr, indices=0)[N - 1])
    print(ans)
except NegativeCycleError:
    print('inf')

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

dist = [float('inf')]*n
dist[0] = 0
for i in range(n-1):
    
    for st, en , score in edges:
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score

negative = [False] * n

for loop in range(n):
    
    
    for e in edges:
        st, en, score = e
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score
            negative[en] = True
        if negative[st]:
            negative[en] = True

if negative[n-1]:
    print('inf')
else:
    print(-dist[n-1])

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

dist = [float('inf')]*n
dist[0] = 0
for i in range(n-1): 
    for st, en , score in edges:
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score

negative = [False] * n

for loop in range(n):
    for e in edges:
        st, en, score = e
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score
            negative[en] = True
        if negative[st]:
            negative[en] = True

if negative[n-1]:
    print('inf')
else:
    print(-dist[n-1])