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):
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point


    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0
        negative = [False for _ in range(self.num_v)]
        for i in range(self.num_v - 1):
            for src in range(self.num_v):
                for dest, cost in self.graph[src].items():
                    if dist[dest] > dist[src] + cost:
                        dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src in range(self.num_v):
                for dest, cost in self.graph[src].items():
                    if dist[dest] > dist[src] + cost:
                        dist[dest] = dist[src] + cost
                        negative[dest] = True
                    if negative[src]:
                        negative[dest] = True
        return dist, negative


n, m = map(int, input().split())
graph = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = -c
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

if negative[-1]:
    print("inf")
else:
    print(-result[-1])

Solution (Python):
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point
        self.negative = [False for _ in range(num_v)]

    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0

        for i in range(self.num_v - 1):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    self.negative[dest] = True
                if self.negative[src]:
                    self.negative[dest] = True
        return dist, self.negative


n, m = map(int, input().split())
graph = []

for i in range(m):
    a, b, c = map(int, input().split())
    graph.append([a - 1, b - 1, -c])
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

if negative[-1]:
    print("inf")
else:
    print(-result[-1])

Solution (Python):
V, E = [int(_) for _ in input().split()]
G = {}

for i in range(V):
    G[i] = {}
for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  
    t -= 1  
    G[s][t] = -c

INF = float('inf')

D = [INF] * V
D[0] = 0  
count = 0
while True:
    count += 1
    update = False
    update_n = False
    for s in G.keys():
        for t in G[s].keys():
            if D[s] != INF and D[t] > D[s] + G[s][t]:
                D[t] = D[s] + G[s][t]
                update = True
                if t == V - 1:
                    update_n = True
    if not update or count == V:
        break
if update_n:
    print('inf')
else:
    print(-D[-1])

Solution (Python):
n, m = map(int, input().split())
d = []
for i in range(m):
    d.append([int(m) for m in input().split()])
e = []
for i in range(m):
    e.append([])
for i in range(m):
    e[i].append(d[i][0] - 1)
    e[i].append(d[i][1] - 1)
    e[i].append(-d[i][2])








"""edge = [[0,1,2],[0,2,5],[1,2,4],[1,3,6],[1,4,10],[2,3,2],[3,5,1],[4,5,3],[4,6,5],[5,6,9],
       [1,0,2],[2,0,5],[2,1,4],[3,1,6],[4,1,10],[3,2,2],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]"""
edge = e

def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    for i in range(num_v):
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
        if i == num_v - 2:
            k = d[-1]
        if i == num_v - 1 and k != d[-1]:
            d[n - 1] = -inf
            break
    return d

print(-shortest_path(edge,n,0)[n - 1])


"""5 5
1 2 2
2 5 4
4 3 1
3 4 2
2 4 1"""

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

Solution (Python):

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

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                if d[b]<d[a]+c:
                    d[b] = d[a]+c
                    update = True
            else:
                update = True
                d[b] = d[a] + c
    if not update:
        break

ans = d[n-1]
updated = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[a]+c>d[b]:
                d[b] = d[a] + c
                if not updated[b]:
                    update = True
                    updated[b] = True
        if updated[a] and not updated[b]:
            update = True
            updated[b] = True
    if not update:
        break

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

Solution (Python):
def BF(N, edges, start):
    D = {}
    P = {}
    for i in range(N):
        P[i] = None
        if i == start:
            D[i] = 0
        else:
            D[i] = float("inf")

    for i in range(N-1):
        for edge in edges:
            a, b, c = edge
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                P[b] = a

    ret = (D, P)

    Nega = {}
    for i in range(N):
        Nega[i] = False
    
    for i in range(N):
        for edge in edges:
            a, b, c = edge
            if Nega[a] == True:
                Nega[b] = True
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                P[b] = a
                Nega[b] = True
        
    return (D, P, Nega)


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

D, P, Nega = BF(N, edges, 0)

if Nega[N-1]:
    print("inf")
else:
    print(-D[N-1])

Solution (Python):
N,M=map(int,input().split())
edges=[]
for m 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
dist_n=[inf for i in range(N)]
negative=[-1 for i in range(N)]
for i in range(N-1):
  for e in edges:
    if dist[e[1]]>dist[e[0]]+e[2]:
      dist[e[1]]=dist[e[0]]+e[2]  
for i in range(N):
  for e in edges:
    if negative[e[0]]>0:
      negative[e[1]]=1
    if dist[e[1]]>dist[e[0]]+e[2]:
      dist[e[1]]=dist[e[0]]+e[2]
      negative[e[1]]=1
if negative[N-1]>0: 
  print(inf)
else:
  print(-dist[N-1])

Solution (Python):
N,M=list(map(int,input().split()))

edge=[[] for _ in range(N)]
dist=[-float('inf') for _ in range(N)]
dist[0]=0

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

tmp=-float('inf')
for n in range(N):
    flag=0
    tmp=dist[-1]
    for i in range(N):
        for b,p in edge[i]:
            if dist[b]<dist[i]+p:
                dist[b]=dist[i]+p
                flag=1
    if flag==0:
        break
if tmp!=dist[-1]:
    print('inf')
else:
    print(int(dist[-1]))

Solution (Python):
V, E=map(int,input().strip().split(' '))
edge=[]
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    edge.append([at,bt,ct])




inf=-3*10**15

def shortest_path(s):
    d=[inf]*V
    d[s]=0
    for _ in range(V+1):
        update=False
        for i in range(E):
            if d[edge[i][0]-1]!=inf and d[edge[i][1]-1]<d[edge[i][0]-1]+edge[i][2]:
                d[edge[i][1]-1]=d[edge[i][0]-1]+edge[i][2]
                update=True
        if update==False:
            break
        if _ == V-1:
            tm=d[V-1]
        if _ == V and d[V-1]!=tm:
            return False
    return d

d=shortest_path(0)
if d==False:
    print('inf')
else:
    print(d[V-1])

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

dist = [float('inf')] * (N+1)
dist[0] = 0

for n in range(N):
    for a, b, c in E:
        if (dist[a] != float('inf')) & (dist[b] > dist[a] + c):
            dist[b] = dist[a] + c
            if (n == N - 1) & (b == N - 1):
                print('inf')
                exit()

print(-dist[N - 1])

Solution (Python):


v,E=map(int,input().split())
e=[]
for i in range(E): 
    f,t,c=map(int,input().split())
    e.append([f-1,t-1,c])
d=[None for i in range(v)]
for i in range(v):
    d[i]=-float('INF')
d[0]=0
for i in range(v-1):
    update=False
    for i in range(E):
        if d[e[i][0]]!=-float('INF') and d[e[i][1]]<d[e[i][0]]+e[i][2]:
            d[e[i][1]]=d[e[i][0]]+e[i][2]
            update=True
    if not update:
        break
ans=d[v-1]
for i in range(E):
    if d[e[i][0]]!=-float('INF') and d[e[i][1]]<d[e[i][0]]+e[i][2]:
        d[e[i][1]]=d[e[i][0]]+e[i][2]
print(ans if ans==d[v-1] else 'inf')

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


def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    MAX_NUM = float('inf')
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


def relax(d, w, source_v, target_v, parent):
    new_cost = d[source_v] + w[source_v][target_v]
    if new_cost < d[target_v]:
        d[target_v] = new_cost
        parent[target_v] = source_v






def bellman_ford(adj, w, s):
    d, parent = initialize_int(adj, s)
    
    for _ in range(len(adj)):
        for vertex in range(len(adj)):
            for neighbor in adj[vertex]:
                relax(d, w, vertex, neighbor, parent)

    
    negative_cycle_edges = set()
    for vertex in range(len(adj)):
        for neighbor in adj[vertex]:
            if d[neighbor] > d[vertex] + w[vertex][neighbor]:
                negative_cycle_edges.add((vertex, neighbor))
    return d, parent, negative_cycle_edges


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    a, b, c = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    c *= -1
    adj[a].append(b)
    w[a][b] = c

d, parent, negative_cycle_edges = bellman_ford(adj, w, 0)
if len(negative_cycle_edges) > 0:
    
    stack = [0]
    visited = set()
    visited.add(0)
    reachable_edges = set()
    while stack:
        source = stack.pop()
        for neighbor in adj[source]:
            if (source, neighbor) in negative_cycle_edges:
                reachable_edges.add((source, neighbor))
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    
    for _, target in reachable_edges:
        stack = [target]
        visited = set()
        visited.add(target)
        while stack:
            source = stack.pop()
            for neighbor in adj[source]:
                if neighbor == N - 1:
                    print("inf")
                    exit(0)
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
    else:
        print(-d[N - 1])
else:
    print(-d[N - 1])

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


def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    MAX_NUM = float('inf')
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


def relax(d, w, source_v, target_v, parent):
    new_cost = d[source_v] + w[source_v][target_v]
    if new_cost < d[target_v]:
        d[target_v] = new_cost
        parent[target_v] = source_v






def bellman_ford(adj, w, s):
    d, parent = initialize_int(adj, s)
    
    for _ in range(len(adj)):
        for vertex in range(len(adj)):
            for neighbor in adj[vertex]:
                relax(d, w, vertex, neighbor, parent)

    
    negative_cycle_edges = set()
    for vertex in range(len(adj)):
        for neighbor in adj[vertex]:
            if d[neighbor] > d[vertex] + w[vertex][neighbor]:
                negative_cycle_edges.add((vertex, neighbor))
    return d, parent, negative_cycle_edges


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    a, b, c = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    c *= -1
    adj[a].append(b)
    w[a][b] = c

d, parent, negative_cycle_edges = bellman_ford(adj, w, 0)
if len(negative_cycle_edges) > 0:
    
    stack = [0]
    visited = set()
    visited.add(0)
    reachable_edges = set()
    while stack:
        source = stack.pop()
        for neighbor in adj[source]:
            if (source, neighbor) in negative_cycle_edges:
                reachable_edges.add((source, neighbor))
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    
    for _, target in reachable_edges:
        stack = [target]
        visited = set()
        visited.add(target)
        while stack:
            source = stack.pop()
            for neighbor in adj[source]:
                if neighbor == N - 1:
                    print("inf")
                    exit(0)
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
    else:
        print(-d[N - 1])
else:
    print(-d[N - 1])

Solution (Python):
import queue

class Graph:

    INF = 10**27+1
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list


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

G = Graph(N,True)

for i in range(M):
    a,b,c = list(map(int,input().split()))
    G.appendEdge(a-1,b-1,-c)
    
res=G.getSSSPwithBellmanFord(0)

if res[2][N-1]:
    print('inf')
else:
    print(-res[0][N-1])

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

N, M = inpl()
inf = float('inf')
path = [0 for _ in range(M)]
score = [-inf]*N
score[0] = 0
ans = 0
for i in range(M):
    a, b, c = inpl()
    path[i] = (a-1,b-1,c)

for i in range(N-1):
    update = False
    for na, nb, nc in path:
        if score[na] != -inf and score[nb] < score[na] + nc:
            score[nb] = score[na]+nc
            update = True
    if not update:
        break
ans = score[N-1]
for na, nb, nc in path:
        if score[na] != -inf and score[nb] < score[na] + nc:
            score[nb] = score[na]+nc
print(ans if ans == score[N-1] else 'inf')

Solution (Python):
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

ans = d[N-1]
for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d[To]>d[From]+cost:
        d[To]=d[From]+cost

if d[N-1]!=ans:
    print('inf')
else:
    print(-ans)

Solution (Python):
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
ans = d[N-1]
for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d[To]>d[From]+cost:
        d[To]=d[From]+cost

if d[N-1]!=ans:
    print('inf')
else:
    print(-ans)

Solution (Python):
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
ans = d[N-1]
for i in range(V):
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost

if d[N-1]!=ans:
    print('inf')
else:
    print(-ans)

Solution (Python):
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in range(m)]
abc=[[t[0],t[1],-t[2]] for t in abc]
def BF(edges,num_v,source):
    
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
  
    
    neg=[False for _ in range(num_v)]
    for i in range(num_v-1):
        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]
    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]
                neg[edge[1]-1]=True
            if neg[edge[0]-1]==True:
                neg[edge[1]-1]=True
    return dist,neg
dis,neg=BF(abc,n,1)

if neg[-1]:
    print("inf")
else:
    print(-dis[-1])

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

INF = float("inf")
d = [INF] * N
d[0] = 0
for i in range(N):
    for a in range(N):
        for b, c in G[a]:
            if d[b] > d[a] + c:
                d[b] = d[a] + c

ne = [False] * N
ans = -d[N - 1]
for i in range(N):
    for a in range(N):
        for b, c in G[a]:
            if d[b] > d[a] + c:
                ne[b] = True
                d[b] = d[a] + c

            if ne[a]:
                ne[b] = True

if ne[N - 1]:
    print("inf")
else:
    print(ans)

Solution (Python):
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 18
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] - c)

ans = dist[N]
for a, b, c in edges:
    dist[b] = min(dist[b], dist[a] - c)

if ans != dist[N]:
    print('inf')
else:
    print(-ans)

Solution (Python):
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 18
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] - c)

ans = dist[N]
for a, b, c in edges:
    dist[b] = min(dist[b], dist[a] - c)

if ans != dist[N]:
    print('inf')
else:
    print(-ans)

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

Cost = [float("inf") for i in range(N)]
V = [False for i in range(N)]
Cost[0] = 0
for i in range(N-1):
    for j in P:
        if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
            if Cost[j[1]] != float("inf"):
                V[j[1]] = True
            Cost[j[1]] = Cost[j[0]] + j[2]     
        if V[j[0]] == True:
            V[j[1]] = True
ans = -Cost[N-1]

for j in P:
    if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
        if Cost[j[1]] != float("inf"):
            V[j[1]] = True
        Cost[j[1]] = Cost[j[0]] + j[2]    
    if V[j[0]] == True:
        V[j[1]] = True

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

Solution (Python):



N, M = map(int, input().split())
INF = float("inf")

G = []

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

dist = [INF for k in range(N)]
dist[0] = 0

for k in range(N-1):
    for l in range(M):
        a, b, c = G[l][0], G[l][1], G[l][2]
        if dist[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c


negative = [0 for k in range(N)]
for k in range(N):
    for l in range(M):
        a, b, c = G[l][0], G[l][1], G[l][2]
        if dist[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            negative[b] = 1
        if negative[a] == 1:
            negative[b] = 1

print("inf" if negative[N-1] else -dist[N-1])

Solution (Python):
inf = int(1e20)
node,edge = map(int,input().split())
ed = []
for i in range(edge):
    e = list(map(int,input().split()))
    ed.append((e[0]-1,e[1]-1,-e[2]))
start = 0
goal = node-1



d = [inf for i in range(node)]
pre = [inf for i in range(node)]
d[start] = 0

for i in range(node):
    update = False
    for e in ed:
        if d[e[0]] != inf and d[e[1]]>d[e[0]]+e[2]:
            d[e[1]] = d[e[0]]+e[2]
            update = True
            pre[e[1]] = e[0]
    if update==False:
        print(-d[goal])
        break
else:
    nowcos = d[goal]
    for i in range(node):
        for e in ed:
            if d[e[0]] != inf and d[e[1]]>d[e[0]]+e[2]:
                d[e[1]] = d[e[0]]+e[2]
                pre[e[1]] = e[0]
    if nowcos != d[goal]:
        print('inf')
    else:
        print(-d[goal])

Solution (Python):
N,M = map(int,input().split())
INF = 10**13
edge = []
for i in range(M):
	a,b,c = map(int,input().split())
	a -= 1
	b -= 1
	edge.append((a, b, -c))

dist = [INF for i in range(N)]
dist[0] = 0

neg_cycle = False
for i in range(N+1):
	update = False
	N_update = False
	for (a,b,c) in edge:
		if dist[a] == INF:
			continue

		if dist[a] + c < dist[b]:
			dist[b] = dist[a] + c
			update = True
			if b == N-1:
				N_update = True

	if not update:
		break
	if i >= N - 1 and N_update:
		neg_cycle = True

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

Solution (Python):
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])


dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i >= n-1 and v == n-1:
                print('inf')
                exit()
    i += 1
    if i > n*2:
        break
print(-dist[-1])

Solution (Python):
ai_ = lambda: [int(x)-1 for x in input().split()]
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

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

for i in range(n):
    for cur_v in range(n):
        for v, c in edge[cur_v]:
            if dist[v] > dist[cur_v] + c:
                dist[v] = dist[cur_v] + c
                if i == n-1 and v == n-1:
                    print('inf')
                    exit()
print(-dist[-1])

Solution (Python):
n, m = list(map(int, input().split()))
infinite = -10**14
score = [infinite for _ in range(n+1)]
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])


is_inf = True
for r in range(n+2): 
    rev = 0
    for i in range(1,n+1):
        for (to, sc) in routes[i]:
            if score[to] < score[i] + sc:
                score[to] = score[i] + sc
                if to == n:
                    rev += 1
    if rev == 0 and r > n:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

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

d = [-10**13 for i in range(n)]
d[0] = 0
flag = [0 for i in range(n)]
flag[0] = 1
d2 = [-10**13 for i in range(n)]
d2[0] = 0
flag2 = [0 for i in range(n)]
flag2[0] = 1

for i in range(n):
    for j in range(m):
        if flag[x[j][0] - 1]:
            d[x[j][1] - 1] = max(d[x[j][1] - 1], d[x[j][0] - 1] + x[j][2])
            flag[x[j][1]-1] = 1

for i in range(2*n+1):
    for j in range(m):
        if flag2[x[j][0] - 1]:
            d2[x[j][1] - 1] = max(d2[x[j][1] - 1], d2[x[j][0] - 1] + x[j][2])
            flag2[x[j][1] - 1] = 1

if d2[n-1] > d[n-1]:
    print("inf")
else:
    print(d[n-1])

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

INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
    for fr,to,cost in es:
        fr,to = fr-1,to-1
        cost *= -1
        if d[fr] != INF and d[to] > d[fr]+cost:
            d[to] = d[fr] + cost
            if i == N-1 and to == N-1:
                print('inf')
                exit()
print(-d[-1])

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

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n,m = li()


adj_list = [[] for _ in range(n)]

for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    adj_list[a].append((c,b))


INF = -10**15
dist = [INF]*n
dist[0] = 0
for j in range(n+1):
    for i in range(n):
        updated = False
        for cost, nex in adj_list[i]:
            bef = dist[nex]
            dist[nex] = max(dist[nex], dist[i]+cost)
            if bef != dist[nex]:
                updated = True
        
    if j == n-1:
        dis_j1 = dist[n-1]
        
    if j == n:
        dis_j = dist[n-1]
        
if dis_j1 != dis_j:
    print("inf")
else:
    print(dis_j)

Solution (Python):
INF = float('inf')
N,M = map(int,input().split())
edge = []
d = [INF]*N
d[0] = 0
negative = [False for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,-c])

for i in range(N):
    for j in range(M):
        if d[edge[j][0]]==INF:
            continue
        d[edge[j][1]] = min(d[edge[j][1]],d[edge[j][0]]+edge[j][2])

ans = d[N-1]

for i in range(N):
    for j in range(M):
        if d[edge[j][0]]==INF:
            continue
        if d[edge[j][1]]>d[edge[j][0]]+edge[j][2]:
            d[edge[j][1]]=d[edge[j][0]]+edge[j][2]
            negative[edge[j][1]] = True
        if negative[edge[j][0]]:
            negative[edge[j][1]] = True
print('inf' if negative[N-1] else -ans)