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):
def bellman_ford():
    n,m=map(int, input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        a,b,c=map(int, input().split())
        g[a-1].append([b-1,-1*c])
    dist = [float("inf")]*n
    inf = float("inf")
    dist[0] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(g[v])):
                edge = g[v][k]
                if(dist[v]!=inf and dist[v]+edge[1] < dist[edge[0]]):
                    dist[edge[0]] = dist[v] + edge[1]

    ans = dist[n-1]
    neg = [0]*n

    for i in range(n):
        for edge in g[i]:
            if(dist[i]==inf):continue
            if(dist[i]+edge[1] < dist[edge[0]]):
                dist[edge[0]] = dist[i]+edge[1]
                neg[edge[0]]=1
            if(neg[i]):
                neg[edge[0]]=1



    if(not neg[n-1]):
        print(dist[n-1]*-1)
    else:
        print("inf")

    return False


def main():
    bellman_ford()
if __name__ == '__main__':
    main()

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

def shortest_path(v, s, edges, inf):
    d = [inf] * v
    d[s] = 0
    for i in range(2 * n):
        update = False
        for frm, to, cost in edges:
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        if i == n:
            memo = d[-1]
    if memo != d[-1]:
        print('inf')
        exit()
    
    return d[-1]

inf = 1e30
print(-shortest_path(n, 0, edges, inf))

Solution (Python):
INF = -float("inf")
 
def Bellmanford(n, e):
  dp = [INF] * n
  dp[0] = 0
  for i in range(n):
    for a, b, c in e:
      if dp[a] != INF and dp[a] + c > dp[b]:
        dp[b] = dp[a] + c
        if i == n-1 and b == n-1:
          return "inf"
  return dp[n-1]

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

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

ans = Bellmanford(N, abc) 
print(ans)

Solution (Python):
import sys
from collections import deque

INF = 10 ** 20
def Bellman_Ford(I):
  N = len(I)
  d = [INF for _ in range(N)] 
  d[0] = 0 
  visited = [0 for _ in range(N)]
  for i in range(N-1):
    update = False 
    task = deque([(0,0,0)])

    visited[0] = i-1
    while task: 
      a, b, c = task.popleft() 
      if d[b] > d[a] + c:
        d[b] = d[a] + c 
        update = True   
      if visited[b] <= i:
        for x, ct in I[b]:
          task.append((b, x, ct))
        visited[b] += 1
    if not update:
        break
        
  
  visited = [0 for _ in range(N)]
  neg = [0 for _ in range(N)]
  for i in range(N):
    update = False 
    task = deque([(0,0,0)])
    visited[0] = i-1
    while task: 
      a, b, c = task.popleft() 
      if d[b] > d[a] + c:
        d[b] = d[a] + c 
        update = True 
        neg[b] = 1
        
      if visited[b] <= i:
        for x, ct in I[b]:
          task.append((b, x, ct))
        visited[b] += 1
        
    if not update:
        break
        
    if neg[N-1] == 1:
      return []
    
  return d

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

d = Bellman_Ford(I)
print(-d[N-1] if d else "inf")

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


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


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


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


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


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


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


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


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


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]


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





N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = IL()
  graph[a-1].append((b-1,-c))
  
s = 0
d = [INF] * N
d[s] = 0
update = True
for _ in range(N):
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        update = True
  if not update:
    break
negative = [False] * N
update = True
for _ in range(N):
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        negative[t] = True
        update = True
  if not update:
    break
if negative[N-1]:
  print("inf")
else:
  print(-d[N-1])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


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


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


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


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


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


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


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


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


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]


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





N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = IL()
  graph[a-1].append((b-1,-c))
  
s = 0
d = [INF] * N
d[s] = 0
update = True
for _ in range(N):
  prevd = d[:]
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        update = True
  if not update:
    break
else:
  if prevd[N-1] == d[N-1]:
    pass
  else:
    d[N-1] = 1 
if d[N-1] == 1:
  print("inf")
else:
  print(-d[N-1])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


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


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


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


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


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


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


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


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


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]


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





N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = IL()
  graph[a-1].append((b-1,-c))
  
s = 0
d = [INF] * N
d[s] = 0
update = True
for _ in range(N):
  prevd = d[:]
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        update = True
  if not update:
    break
else:
  if prevd[N-1] == d[N-1]:
    pass
  else:
    d[N-1] = -INF 
  
print(-d[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-1, b-1, c))


inf = float("inf")
dist = [-inf for i in range(N)]
dist[0] = 0
is_cycle = False


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

ans = dist[-1] if not is_cycle else 'inf'
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict
    n, m = map(int, readline().split())
    edge = []

    for _ in range(m):
        a, b, c = map(int, readline().split())
        edge.append((a - 1, b - 1, -c))

    dist = [INF] * n
    dist[0] = 0

    for i in range(n - 1):
        for a, b, c in edge:
            dist[b] = min(dist[b], dist[a] + c)

    loop = [False] * n
    for i in range(n):
        for a, b, c in edge:
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                loop[b] = True

    if loop[n - 1]:
        print("inf")
    else:
        print(-dist[n - 1])


if __name__ == '__main__':
    main()

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

def Bellmanford(n, edges):
    dp = [INF] * n
    dp[0] = 0

    for i in range(n):  
        for u, v, c in edges:
            if dp[u] != INF and dp[u] + c > dp[v]:
                dp[v] = dp[u] + c
                if i == n-1 and v == n-1:
                    return "inf"

    return dp[n-1]


N, M = map(int, input().split())
E = []

for i in range(M):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, c))

ans = Bellmanford(N, E)

print(ans)

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

def Bellmanford(n, edges):
    dp = [INF] * n
    dp[0] = 0

    for i in range(n):  
        for u, v, c in edges:
            if dp[u] != INF and dp[u] + c < dp[v]:
                dp[v] = dp[u] + c
                if i == n-1 and v == n-1:
                    return "inf"

    return -dp[n-1]


N, M = map(int, input().split())
E = []

for i in range(M):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, -c))

ans = Bellmanford(N, E)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
e = [set() for _ in range(N + 1)]
reve = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].add((v, -c))
  reve[v].append(u)

vis = [0] * (N + 1)
def revdfs(x):
  global vis
  if x == 1: return True
  res = 0
  for y in reve[x]:
    if vis[y]: continue
    vis[y] = 1
    res |= revdfs(y)
  return res
def dfs(x):
  global vis
  if x == N: return True
  res = 0
  for y, _ in e[x]:
    if vis[y]: continue
    vis[y] = 1
    res |= dfs(y)
  return res
banned = [0] * (N + 1)
for x in range(1, N + 1):
  vis = [0] * (N + 1)
  banned[x] |= revdfs(x) ^ 1
  vis = [0] * (N + 1)
  banned[x] |= dfs(x) ^ 1

for x in range(1, N + 1):
  t = list(e[x])
  for y, d in t:
    if banned[x] | banned[y]: e[x].discard((y, d))

INF = 10**18
dist = [INF] * (N + 1)
dist[1] = 0
update = 1
for _ in range(N + 1):
    update = 0
    for v, x in enumerate(e):
        for t, cost in x:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
  print("inf")
  exit(0)
print(-dist[N])

Solution (Python):
n, m = map(int, input().split())

edges = [list(map(int, input().split())) for _ in range(m)]

score = [-float('inf')] * (n+1)
score[1] = 0
cnt = 0

for i in range(n):
    for frm, to, cost in edges:
        if score[to] < score[frm] + cost:
            if i == n - 1 and to == n:
                print('inf')
                exit()
            score[to] = score[frm] + cost

print(score[n])

Solution (Python):
"""
頂点1から頂点Nまでのルートの途中でサイクルがあれば、無限にスコアを大きくできる。
サイクルがない場合、V-1回でNまでのスコアが求まる。
サイクルがある場合、もう一周回すと、Nまでのスコアが増えているはず。
Nのスコアが増えたらサイクル有、ということ
"""
N,M = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(M)]
dp = [-1*float("INF")]*(N+1)
dp[1] = 0

for _ in range(N-1):
    for a,b,c in edges:
        dp[b] = max(dp[b],dp[a]+c)

tmp1 = dp[N]

for _ in range(N-1):
    for a,b,c in edges:
        dp[b] = max(dp[b],dp[a]+c)

tmp2 = dp[N]
if tmp2 > tmp1:
    print("inf")
else:
    print(tmp1)

Solution (Python):
def bellman_ford(s):
    d = [-float("inf")]*n 
    d[s] = 0 
    check = [False]*n
    for i in range(n):
        update = False 
        for x, y, z in g:
            if d[y] < d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        
        if i == n - 1:
          for x, y, z in g:
            if d[y] < d[x] + z:
                d[y] = d[x] + z
                check[x]=True
                check[y]=True
    if check[n-1]:
      return "inf"
    return d[n-1]

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

Solution (Python):

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

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            
            if i == N - 1 and nn == N:
                print("inf")
                sys.exit()
            cost[nn] = cost[n] + c

print(cost[N])

Solution (Python):
import sys
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            
            if i == N - 1 and nn == N:
                print("inf")
                sys.exit()
            cost[nn] = cost[n] + c

print(cost[N])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
    INF = 10 ** 40
    S = [-INF] * N
    S[0] = 0

    def helper(n, s, hist):
        for g, gc in G[n]:
            if S[g] >= s + gc or S[g] >= INF:
                continue
            S[g] = s + gc
            if g in hist:
                S[g] = INF
            hist[g] = hist.get(g, 0) + 1
            helper(g, S[g], hist)
            hist[g] -= 1
            if hist[g] == 0:
                del hist[g]
    helper(0, 0, {0: 1})
    s = S[-1]
    return s if s < INF else 'inf'

print(main())

Solution (Python):
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
import sys
buf = sys.stdin.buffer


def main():
    n, m = map(int, buf.readline().split())
    ABC = map(int, buf.read().split())

    edges = []
    routes = [[] for _ in range(n)]
    rev_routes = [[] for _ in range(n)]

    def get_reachable_nodes(start, routes):
        seen = {start}
        todo = []
        for to in routes[start]:
            todo.append(to)
            seen.add(to)

        while todo:
            node = todo.pop()
            for to in routes[node]:
                if to in seen:
                    continue
                todo.append(to)
                seen.add(to)
        return seen

    for node1, node2, value in zip(ABC, ABC, ABC):
        node1, node2 = node1 - 1, node2 - 1
        edges.append([node1, node2, -value])
        routes[node1].append(node2)
        rev_routes[node2].append(node1)

    from_start = get_reachable_nodes(0, routes)
    to_goal = get_reachable_nodes(n-1, rev_routes)
    from_start_to_goal = from_start & to_goal

    values = []
    rows = []
    cols = []

    for row, col, minus_value in edges:
        if {row, col} <= from_start_to_goal:
            values.append(minus_value)
            rows.append(row)
            cols.append(col)

    graph = coo_matrix((values, (rows, cols)), shape=(n, n))
    try:
        bf = bellman_ford(graph, indices=[0])
        print(-int(bf[0][n - 1]))
    except NegativeCycleError:
        print("inf")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
S=sys.stdin.readlines()
N,M=map(int,S[0].split())
G=[]
a,b,c=0,0,0
for i in range(M):
  a,b,c=map(int,S[i+1].split())
  G.append((a-1,b-1,-c))
INF=10**15
D=[INF]*N
D[0]=0
e=0
for i in range(N-1):
  for j in range(M):
    e=G[j]
    if D[e[0]]!=INF and D[e[1]]>D[e[0]]+e[2]:
      D[e[1]]=D[e[0]]+e[2]
X=D[N-1]
for j in range(M):
  e=G[j]
  if D[e[0]]!=INF and D[e[1]]>D[e[0]]+e[2]:
    D[e[1]]=D[e[0]]+e[2]
if X==D[N-1]:
  print(-X)
else:
  print('inf')

Solution (Python):
N,M = map(int,input().split())
edges = []
for _ in range(M):
    s,t,d = map(int,input().split())
    edges.append((s,t,d))

cost = [-1*float("INF") for _ in range(N+1)]
cost[1] = 0
count = 0
while count < N:
    count += 1
    for s,t,d in edges:
        if cost[s] + d > cost[t]:
            cost[t] = cost[s] + d
ans = cost[N]

negative = [False]*(N+1)
count = 0
while count <= N:
    count += 1
    for s,t,d in edges:
        if cost[s] + d > cost[t]:
            cost[t] = cost[s] + d
            negative[t] = True
for s,t,d in edges:
        if negative[s]:
            negative[t] = True

if negative[N]:
    print("inf")
else:
    print(ans)

Solution (Python):
class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.deg[e[1] - indexed] += 1

    def bellman_ford(self, s, t=None, INF=10**18):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        update = True
        for i in range(self.n):
            update = False
            for node, g in enumerate(self.graph):
                for adj, adjcost in g:
                    if dist[node] != INF and dist[node] + adjcost < dist[adj]:
                        dist[adj] = dist[node] + adjcost
                        update = True
            if not update:
                return dist[t] if t is not None else dist
        if t is None:
            return
        negative_cycle = [0 for _ in range(self.n)]
        for i in range(self.n):
            for node, g in enumerate(self.graph):
                for adj, adjcost in g:
                    if dist[node] != INF and dist[node] + adjcost < dist[adj]:
                        dist[adj] = dist[node] + adjcost
                        negative_cycle[adj] = True
        if not negative_cycle[t]:
            return dist[t]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = []

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

g = Graph(N, E)
bf = g.bellman_ford(0, N - 1)

print(-bf if bf is not None else 'inf')

Solution (Python):
class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.deg[e[1] - indexed] += 1

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

    def bellman_ford(self, s, t=None, INF=10**18):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        update = True
        for i in range(self.n):
            update = False
            for node, g in enumerate(self.graph):
                for adj, adjcost in g:
                    if dist[node] != INF and dist[node] + adjcost < dist[adj]:
                        dist[adj] = dist[node] + adjcost
                        update = True
            if not update:
                return dist[t] if t is not None else dist
        if t is None:
            return
        negative_cycle = [0 for _ in range(self.n)]
        for i in range(self.n):
            for node, g in enumerate(self.graph):
                for adj, adjcost in g:
                    if dist[node] != INF and dist[node] + adjcost < dist[adj]:
                        dist[adj] = dist[node] + adjcost
                        negative_cycle[adj] = True
        if not negative_cycle[t]:
            return dist[t]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = []

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

g = Graph(N, E)
bf = g.bellman_ford(0, N - 1)

print(-bf if bf is not None else 'inf')

Solution (Python):
n,m=map(int,input().split())

abc=[list(map(int,input().split())) for _ in range(m)]
abc=[[a-1,b-1,-c] for a,b,c in abc]


def BellmanFord(edges,num_v,source):
  
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source]=0  
  
  for i in range(num_v):
    for edge in edges:
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        
  negative=[False]*n
  for i in range(num_v):
    for edge in edges:
      if negative[edge[0]]:negative[edge[1]]=True
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        negative[edge[1]] = True
  return dist[n-1],negative[n-1]
c,d=BellmanFord(abc,n,0)

if d:
  print('inf')
else:
  print(-c)

Solution (Python):
n, m = map(int, input().split())

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    
    for i in range(n*2):
        for edge in g:
            if edge[0] != float('inf') and d[edge[1]] > d[edge[0]] + edge[2]:
                d[edge[1]] = d[edge[0]] + edge[2]
                if i>=n-1 and edge[1] == n-1:
                    return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')