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):
INF=10**30
def Belman_Ford(s,N,Edge):
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg
                
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))
dist,neg=Belman_Ford(0,N,Edge)

if(neg[N-1]):
    print('inf')
else:
    print(-dist[N-1])

Solution (Python):
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
    if i == N-2:
      t = score[N-1]
    if i == N-1:
      if t != score[N-1]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(t)
else:
    print('inf')

Solution (Python):
V,M = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(M)]
G = [list() for i in range(V)]
for a,b,c in abc:
    G[b-1].append((a-1,-c))
INF = 10**18
dist = [INF] * V
dist[V-1] = 0
update = 1
for _ in range(V):
    update = 0
    for v, e in enumerate(G):
        for t, cost in e:
            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()
print(-dist[0])

Solution (Python):
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[f]!=INF and dist[t]>dist[f]+c:
                dist[t]=min(dist[t],dist[f]+c)
    F=[False]*N
    for j in range(N):
        for f,t,c in Edge:
            if(dist[t]>dist[f]+c):
                dist[t]=dist[f]+c
                F[t]=True
    if F[N-1]:
        return 'inf'
    else:
        return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Solution (Python):
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if dist[f]!=INF:
                    dist[t]=min(dist[t],dist[f]+c)
                    update=True
                    if cnt==N-1 and t==N-1:
                        print('inf')
                        exit()
        if not update or cnt==N-1:
            break
        cnt+=1
    return -dist[N-1]
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
abc = [tuple(na()) for i in range(m)]

dp = [float('inf')]*n
dp[0] = 0

for i in range(n):
    for a,b,c in abc:
        a,b,c = a-1,b-1,-c
        if dp[a] != float('inf') and dp[b] > dp[a] + c:
            dp[b] = dp[a] + c
            if i == n-1 and b == n-1:
                print('inf')
                exit()

print(-dp[-1])

Solution (Python):
def resolve():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(m)]
    a = [[x, y, -z] for x, y, z in a]
    print(BF(a, n, 1)[-1])


def BF(p, n, s):
    inf = float("inf")
    d = [inf for i in range(n)]
    d[s-1] = 0
    for i in range(n+1):
        for e in p:
            if e[0] != inf and d[e[1]-1] > d[e[0]-1]+e[2]:
                d[e[1]-1] = d[e[0]-1] + e[2]
        if i == n-1:
            t = d[-1]
        if i == n and t != d[-1]:
            return [0, 'inf']
    return list(map(lambda x: -x, d))


if __name__ == "__main__":
    resolve()

Solution (Python):
class BellmanFord:
    def __init__(self,v,start):
        self.inf = float('inf')
        self.dist = [self.inf]*v
        self.dist[start] = 0
        self.edge = []
        self.v = v
    
    def add(self,f,t,cost):
        self.edge.append((f,t,cost))
    
    def build(self,gorl):
        for _ in range(self.v - 1):
            for f,t,cost in self.edge:
                if self.dist[t] > self.dist[f] + cost:
                    self.dist[t] = self.dist[f] + cost
        self.ans = self.dist[gorl]
        for f,t,cost in self.edge:
            if self.dist[t] > self.dist[f] + cost:
                self.dist[t] = self.dist[f] + cost
        return self.ans if self.ans == self.dist[gorl] else '-inf'

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

bf = BellmanFord(n,0)

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

ans = bf.build(n-1)
if ans == '-inf':
    print('inf')
else:
    print(- ans)

Solution (Python):
class BellmanFord:
    def __init__(self,v,start):
        self.inf = float('inf')
        self.dist = [self.inf]*v
        self.dist[start] = 0
        self.edge = []
        self.v = v
    
    def add(self,f,t,cost):
        self.edge.append((f,t,cost))
    
    def build(self):
        for _ in range(self.v - 1):
            for f,t,cost in self.edge:
                if self.dist[t] > self.dist[f] + cost:
                    self.dist[t] = self.dist[f] + cost
        self.ans = self.dist[n-1]
        for f,t,cost in self.edge:
            if self.dist[t] > self.dist[f] + cost:
                self.dist[t] = self.dist[f] + cost
        return self.ans == self.dist[n-1]

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

bf = BellmanFord(n,0)

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

if bf.build():
    print(- bf.ans)
else:
    print('inf')

Solution (Python):
import sys

N, M = map(int,input().split())
es = []
for _ in range(M):
    e = list(map(int,input().split()))
    e[2] *= -1
    es.append(e)

INF = float('inf')
d = [INF for _ in range(N+1)]
d[1] = 0
negative = [0 for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        e = es[j]
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                negative[e[0]] = 1
                negative[e[1]] = 1
for i in range(M):
    e = es[i]
    if negative[e[0]]:
        negative[e[1]] = 1
if negative[N]:
    print('inf')
else:
    print(-d[N])

Solution (Python):

import io

nim,mike=map(int,input().split())

abc=[list(map(int,input().split())) for _ in [0]*mike]

g=[[] for _ in [0]*nim]
[g[a-1].append([b-1,c]) for a,b,c in abc]

dist=[-10**15 for _ in [0]*nim]
dist[0]=0
a,b=-10**15,-10**15

for _ in range(nim):
    for p in range(nim):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j)
    a,b=b,dist[nim-1]

if a==b:
    print(a)
else:
    print("inf")

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

def bellmanford(G, s):
    n = len(G)
    inf = -float('inf')
    dist = [inf] * n
    dist[s] = 0
    for i in range(n):
        for v in range(n):
            for w, c in G[v]:
                if dist[w] < dist[v] + c:
                    dist[w] = dist[v] + c
                    if i >= n - 1 and w == n - 1:
                        return -1
    return dist

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append((b, c))
    dist = bellmanford(graph, 0)
    if dist == -1:
        print("inf")
    else:
        print(dist[N-1])

if __name__ == '__main__':
    main()

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

def bellmanford(G, s):
    n = len(G)
    inf = -float('inf')
    dist = [inf] * n
    dist[s] = 0
    for i in range(2*n):
        for v in range(n):
            for w, c in G[v]:
                if dist[w] < dist[v] + c:
                    dist[w] = dist[v] + c
                    if i >= n - 1 and w == n-1:
                        return -1
    return dist

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append((b, c))
    dist = bellmanford(graph, 0)
    if dist == -1:
        print("inf")
    else:
        print(dist[N-1])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m = myinput()
abc = mylistinput(m)

for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = -1 * abc[i][2]
    abc[i][0] = a
    abc[i][1] = b
    abc[i][2] = c


















def BellmanFord(s,n,w,es):
    
    d = [float("inf")]*n
    d[s] = 0
    
    for i in range(n):
        
        for p,q,r in es:
            
            if d[p]!=float("inf") and d[q]>(d[p]+r):
                d[q] = d[p] + r
                
                if i==(n-1) and q==(n-1):
                    return False,[]
        
        
        
        
    return True,d
















flag,distance = BellmanFord(0,n,m,abc)
if flag:
    print(-1*distance[n-1])
else:
    print("inf")

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

N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a, b, -c))
dist = [float('inf')] * (N+1)
dist[1] = 0
for _ in range(N-1):
    for u, v, weight in edges:
        if dist[v] > dist[u] + weight:
            dist[v] = dist[u] + weight
negative = [False] * (N+1)
for _ in range(N):
    for u, v, weight in edges:
        if dist[v] > dist[u] + weight:
            dist[v] = dist[u] + weight
            negative[v] = True
print('inf' if negative[N] else -dist[N])

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

stack = [0]
can_reach = [0]*n
while stack:
    v = stack.pop()
    if can_reach[v]:
        continue
    can_reach[v] = 1
    for v2 in forward_edges[v]:
        if can_reach[v2]:
            continue
        stack.append(v2)

INF = 10**18
dist = [INF]*n
dist[0] = 0
for i in range(n-1):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        if not can_reach[v2]:
            continue
        dist[v2] = -INF
        negative[v2] = 1


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

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

stack = [0]
can_reach = [0]*n
while stack:
    v = stack.pop()
    if can_reach[v]:
        continue
    can_reach[v] = 1
    for v2 in forward_edges[v]:
        if can_reach[v2]:
            continue
        stack.append(v2)

INF = 10**18
dist = [INF]*n
dist[0] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n*2):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        if not can_reach[v2]:
            continue
        dist[v2] = -INF
        negative[v2] = 1

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

Solution (Python):
from collections import deque


def main():

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

    
    G = [set() for _ in range(N)]
    for i in range(M):
        E[i][0], E[i][1] = E[i][0] - 1, E[i][1] - 1
        G[E[i][0]].add(E[i][1])

    def bfs(s):
        
        vis_loc = [False] * N
        vis_loc[s] = True
        q = deque([s])
        while len(q):
            v = q.popleft()
            for n in G[v]:
                if vis_loc[n]:
                    continue
                q.append(n)
                vis_loc[n] = True
        return vis_loc
    vis = bfs(0)
    C = []
    for i in range(M):
        if vis[E[i][0]]:
            C.append(i)

    
    N_con = sum(vis)
    ans = [float('inf')] * N
    ans[0] = 0
    for i in range(N_con):
        ud = -1
        for j in C:
            a, b, c = E[j]
            if ans[b] > ans[a] - c:
                ans[b] = ans[a] - c
                ud = a
        if ud == -1:
            break
        else:
            if i == N_con - 1:
                if bfs(ud)[N - 1]:
                    print('inf')
                    exit()
    print(-ans[N - 1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys


N, M = map(int, input().split())
edge = []
for s in sys.stdin.readlines():
    a, b, c = map(int, s.split())
    edge.append((a - 1, b - 1, c))

path = [-float('inf')] * N
path[0] = 0

for i in range(N - 1):
    for j in range(M):
        a, b, c = edge[j]
        if path[b] < path[a] + c:
            path[b] = path[a] + c


for i in range(N - 1):
    for j in range(M):
        a, b, c = edge[j]
        if path[b] < path[a] + c:
            path[b] = float('inf')

print(path[-1])

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

init_v = 0
INF = float('inf')
dist = [INF]*n
dist[init_v] = 0
negative_cycle = 0
for i in range(2*n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c
        if i >= n-1 and v2 == n-1:
            negative_cycle = 1

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

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

init_v = 0
INF = float('inf')
dist = [INF]*n
dist[init_v] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c
        negative[v2] = 1

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

Solution (Python):
def bellman_ford(edges, N, start, end):
    cost = [float("inf") for _ in range(N)]
    cost[start] = 0
    negative = [False for _ in range(N)]

    for i in range(N):
        for j in range(len(edges)):
            fro, to, c = edges[j]

            if cost[to] > cost[fro] + c:
                cost[to] = cost[fro] + c
                
                if i == N - 1:
                    negative[to] = True

    if negative[end]:
        return "inf"
    else:
        return -cost[end]


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

cost = [float("inf") for _ in range(N)]
start = 0
end = N - 1
print(bellman_ford(edges, N, start, end))

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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



def find_negative_loop(n,w,es):
    
    
    d = [float("inf")] * n
    d[0] = 0 
    
    for i in range(n-1):
        for j in range(w):
            e = es[j]
            if d[e[1]-1] > d[e[0]-1] - e[2]:
                d[e[1]-1] = d[e[0]-1] - e[2]
    neg=[False]*n
    for i in range(n):
        for j in range(w):
            e=es[j]
            if d[e[1]-1] > d[e[0]-1] - e[2]:
                d[e[1]-1] = d[e[0]-1] - e[2]
                neg[e[1]-1]=True
            if neg[e[0]-1]==True:
                neg[e[1]-1]=True
    return (d,neg)



ans=find_negative_loop(n,m,abc)
if ans[1][-1]==True:
    print("inf")
else:
    print(-ans[0][-1])

Solution (Python):

class BellmanFord():
    """ベルマンフォード法で最短経路を求める"""
    def __init__(self, s, V):
        """
        Args:
            s(int): 始点
            V(int): 頂点数
        """
        self.graph = {}
        for i in range(V):
            self.graph[i] = []
        self._V = V
        self.dst = [float("inf") for _ in range(V)]
        self.dst[s] = 0

    @property
    def dist(self):
        return self.dst

    @property
    def V(self):
        return self._V

    def add(self, a, b, cost):
        """頂点aから頂点bへのコストはcost"""
        self.graph[a].append((b, cost))

    def shortest_path(self):
        """始点sからの最短経路を求める
        Returns:
            (bool): 負の閉路が存在する(True) / 存在しない(False)
        """
        for t in range(self.V):
            update = False
            for u in range(self.V):
                if self.dst[u] == float("inf"): continue
                for v, cost in self.graph[u]:
                    if self.dst[v] > self.dst[u] + cost:
                        self.dst[v] = self.dst[u] + cost
                        update = True

                        if t == self.V-1 and v == self.V-1:
                            return True

            if not update:
                break

        return False


def solve():
    N, M = map(int, input().split())
    bf = BellmanFord(0, N)

    for _ in range(M):
        a, b, c = map(int, input().split())
        bf.add(a-1, b-1, -c)

    nloop = bf.shortest_path()

    if nloop:
        print("inf")
    else:
        print(-bf.dist[N-1])


if __name__ == "__main__":
    solve()

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[v]>d[u]+c:
        d[v]=d[u]+c
        if i==n-1 and v==n-1:
          return 'inf'
  return (-1)*d[n-1]
n,m=map(int,input().split())
edges=[0]*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):
def bellmanford(s, n, es):
    
    
    d = [float("inf")] * n
    neg = [False]*n
    d[s] = 0

    for i in range(n):
        for p, q, r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                if i == n-1:
                    neg[q] = True
    return d, neg


n, w = map(int, input().split())  
es = []

for _ in range(w):
    x, y, z = map(int, input().split())
    es.append([x-1, y-1, -z])

d, neg = bellmanford(0, n, es)
if neg[-1]:
    print("inf")
else:
    print(-d[-1])

Solution (Python):


from collections import deque

def bfs(s, graph):
    visited = [False]*N
    visited[s] = True
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv in graph[v]:
            if not visited[nv]:
                visited[nv] = True
                q.append(nv)
    
    return visited

def bellmanford():
    dist = [10**18]*N
    dist[0] = 0
    
    for i in range(N):
        for s, t, c in edges:
            if not visited1[s] or not visited2[t]:
                continue
            
            if dist[t]>dist[s]+c:
                dist[t] = dist[s]+c
                
                if i==N-1:
                    print('inf')
                    exit()

    return dist[-1]

N, M = map(int, input().split())
edges = []
G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]

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

visited1 = bfs(0, G)
visited2 = bfs(N-1, rG)

print(-bellmanford())

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 (-1)*d[n-1]

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

for i in range(M):
  a,b,c=map(int, sys.stdin.readline().split())
  Edges[i]=(a-1,b-1,-c)
    
ans=Bellmanford(N,Edges,0)
print(ans)

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

def readlines(n):
    for _ in range(n):
        a, b, c = map(int, input().split())
        yield a, b, c

def main():
    n, m = map(int, input().split())
    edges = [(a-1, b-1, -c) for a, b, c in readlines(m)]
    costs = bellman_ford(0, edges, n)

    if costs == -1:
        print("inf")
    else:
        print(-costs[-1])

def bellman_ford(start, edges, n):
    inf = float("inf")
    costs = [inf] * n
    costs[start] = 0
    for i in range(n):
        for u, v, weight in edges:
            if costs[u] + weight < costs[v]:
                costs[v] = costs[u] + weight
                if i == n - 1 and v == n - 1:
                    return -1

    return costs

main()

Solution (Python):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  
        self._E = 0  
        self._V = V  

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  
                    heapq.heappush(que, (d[e.to], e.to))  
        return d

def BellmanFord(edges,num_v,source):
  
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0

  
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and 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: return -1

  return dist

N,M=map(int,input().split())
edges=[]
test=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    edges.append([a,b,-c])
    test.add(b-1,a-1,1)

use=set([N-1])
for i in range(0,N-1):
    if test.shortest_path(N-1)[i]!=10**15:
        use.add(i)

useedges=[]
for i in range(0,M):
    a,b,c=edges[i]
    if a-1 in use and b-1 in use:
        useedges.append(edges[i])

ans=BellmanFord(useedges,N,1)
if ans==-1:
    print('inf')
else:
    print(-ans[N-1])

Solution (Python):
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = dict()

    def add_edge(self, _from, _to, _cost):
        self.edge[(_from, _to)] = _cost

    def fill_cost(self, check=False):
        negative_loops = set()
        for i in range(self.n):
            for (_from, _to), _cost in self.edge.items():
                if self.cost[_from] != INF and self.cost[_to] > self.cost[_from] + _cost:
                    self.cost[_to] = self.cost[_from] + _cost
                    if check:
                        negative_loops.add(_to)
        return negative_loops


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)
bf.fill_cost()
negative_loops = bf.fill_cost(check=True)

if N - 1 in negative_loops:
    print('inf')
else:
    print(-bf.cost[-1])

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

def bellman_ford(s):
  
  
  dist = [float('inf')]*n 
  dist[s] = 0
  for u in range(n):
    for s, t, d in std:
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d
        if u == n-1 and t == n-1:
          return -1
  return dist

dist = bellman_ford(0)
if dist != -1:
  print(-dist[n-1])
else:
  print('inf')

Solution (Python):
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1 and v == V-1:
                        return -1
        return dist
    

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    dist = bf.bellmanford(0,N,E)
    if dist == -1:
        print('inf')
    else:
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

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

dist = [-10 ** 18] * n
dist[0] = 0

def update():
    global dist
    for a, b, c in abc:
        if dist[a] + c > dist[b]:
            dist[b] = dist[a] + c

for _ in range(n):
    update()
a = dist[-1]
for _ in range(n):
    update()
b = dist[-1]
if a != b:
    print("inf")
else:
    print(a)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M = map(int, rl().split())
    graph = []
    for _ in range(M):
        a, b, c = map(int, rl().split())
        a -= 1
        b -= 1
        c *= -1
        graph.append([a, b, c])
    
    def bellman_ford(s):
        dist_ls = [10 ** 15] * N
        dist_ls[s] = 0
        for i in range(N):
            for u, v, w in graph:
                if dist_ls[u] + w < dist_ls[v]:
                    dist_ls[v] = dist_ls[u] + w
                    if i == N - 1 and v == N - 1:
                        return -1
        return dist_ls
    
    dist = bellman_ford(0)
    if dist == -1:
        print('inf')
    else:
        print(-dist[-1])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M = map(int, rl().split())
    graph = []
    for _ in range(M):
        a, b, c = map(int, rl().split())
        a -= 1
        b -= 1
        c *= -1
        graph.append([a, b, c])
    
    def bellman_ford(s):
        dist_ls = [10 ** 15] * N
        dist_ls[s] = 0
        for i in range(N):
            for s, t, w in graph:
                if dist_ls[s] + w < dist_ls[t]:
                    dist_ls[t] = dist_ls[s] + w
                    if i == N - 1 and t == N - 1:
                        return -1
        return dist_ls
    
    dist = bellman_ford(0)
    if dist == -1:
        print('inf')
    else:
        print(-1 * dist[-1])


if __name__ == '__main__':
    solve()

Solution (Python):
N, M = list(map(int, input().split()))
sides = []
for i in range(M):
    sides.append(list(map(int, input().split())))

costs = [-(10**20)]*N
costs[0] = 0

epoch = 0
update_number = 1
L = 0

while update_number > 0 and epoch < 2*(N-1):
    update_number = 0
    for side in sides:
        if costs[side[1]-1] < costs[side[0]-1]+side[2]:
            costs[side[1]-1] = costs[side[0]-1]+side[2]
            update_number += 1
    epoch += 1
    if epoch == N-1:
        L = costs[N-1]

if epoch == 2*(N-1) and L != costs[N-1]:
    print('inf')
else:
    print(costs[N-1])