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**50
n,m = map(int, input().split())

ea = []
eb = []
cost = []

for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    ea.append(a)
    eb.append(b)
    cost.append(-c)

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            update = True
    if not update:
        break

ans = d[n-1]
negative = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            if not negative[b]:
                update = True
            negative[b] = True
        if negative[a] and not negative[b]:
            negative[b] = True
            update = True
    if not update:
        break

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

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

def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    ansn_1 = neg
    ans_n = neg
    
    for i in range(n+1):
        for frm, node in enumerate(graph):
            for cost, to in node:
                dist[to] = max(dist[to], dist[frm] + cost)
        
        if i == n-1:
            ansn_1 = dist[-1]
        elif i == n:
            ans_n = dist[-1]
            
    if ansn_1 != ans_n:
        return "inf"
    else:
        return ans_n
        

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    
ans = bf(graph)
print(ans)

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


def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    
    hasUpdate = True
    cnt = 0
    cur = neg
    while hasUpdate:
        hasUpdate = False
        cnt += 1
        
        for frm, node in enumerate(graph):
            for cost, to in node:
                bef = dist[to]
                dist[to] = max(dist[to], dist[frm] + cost)
                
                
                if dist[to] != bef:
                    hasUpdate = True
        
        if cnt == n-1:
            cur = dist[-1]
            
        if cnt == n:
            if dist[-1] == cur:
                return dist[-1]
            else:
                return "inf"
        
    return dist[-1]
                

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    
ans = bf(graph)
print(ans)

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


def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    
    hasUpdate = True
    cnt = 0
    cur = neg
    while hasUpdate:
        hasUpdate = False
        cnt += 1
        
        for frm, node in enumerate(graph):
            for cost, to in node:
                bef = dist[to]
                dist[to] = max(dist[to], dist[frm] + cost)
                
                
                if dist[to] != bef:
                    hasUpdate = True
        
        if cnt == n:
            cur = dist[-1]
            
        if cnt == n+1:
            if dist[-1] == cur:
                return dist[-1]
            else:
                return "inf"
        
    return dist[-1]
                

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    
ans = bf(graph)
print(ans)

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


class BellmanFord(object):
    def __init__(self, edges, n_nodes, start):
        self.edges = edges
        dist = [float('inf')] * n_nodes
        dist[start] = 0
        prev = [None] * n_nodes

        for _ in range(n_nodes - 1):
            for u, v, weight in edges:
                if dist[u] == float('inf'):
                    continue
                if dist[v] > dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
        self.dist = dist
        self.prev = prev

    def check(self, goal=None):
        if goal is None:
            for u, v, weight in self.edges:
                if self.dist[v] > self.dist[u] + weight:
                    return False
            return True
        else:
            negative = [False] * N
            for _ in range(N):
                for u, v, weight in self.edges:
                    if self.dist[u] == float('inf'):
                        continue
                    if negative[u] or self.dist[v] > self.dist[u] + weight:
                        negative[v] = True
            return not negative[goal]


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

bf = BellmanFord(edges, N, 0)
if bf.check(N - 1):
    print(-bf.dist[N - 1])
else:
    print('inf')

Solution (Python):
n,m=map(int,input().split())
inf=float("inf")
l=[tuple(map(int,input().split())) for i in range(m)]
 
d=[inf]*n
d[0]=0

for i in range(n):
  for a,b,c in l:
    a,b,c=a-1,b-1,-c
    if d[a]!=inf and d[b]>d[a]+c:
      d[b]=d[a]+c
      if i==n-1 and b==n-1:
        print("inf")
        exit()
print(-d[-1])

Solution (Python):
'''
V, E : Vは頂点数、Eは辺数
nodes : e = [from, to, cost] を要素とする辺のリスト（有向辺）
☆負のループがあっても、それがゴールと非連結な場所にあった場合関係ない。
つまり「0→負のループ→N-1」という経路が存在するときのみ問題になる。
0→負のループ、という経路があるかどうかは0からの距離がfloat('inf')でないことで調べられる
負のループのある点→N-1という経路があるかどうかは、更新の際にnegative[i]から辺が伸びている頂点も更新することで調べられる。
'''
V, E = map(int, input().split())
nodes = []
for _ in range(E):
    e_from, e_to, e_cost = map(int, input().split())
    e_from -= 1
    e_to -= 1 
    e_cost *= -1
    nodes.append([e_from, e_to, e_cost])

d = [float('inf')] * V
negative = [False] * V
d[0] = 0
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            negative[e[1]] = True
        if negative[e[0]]:
            negative[e[1]] = True

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

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))


def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(2*N): 
		will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			if not upd8s[s]: continue	
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					will_upd8s[t] = True 

		if not upd8: 
			return Costs[Goal]

		if i == N-1: 
			tmp = Costs[Goal]

		upd8s = will_upd8s[:]

	if tmp != Costs[Goal]:
		return -INF
	else:
		return Costs[Goal]

print(-BellmanFord(0,N-1))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N): 
		will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			if not upd8s[s]: continue	
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					will_upd8s[t] = True 

		upd8s = will_upd8s[:]
		if not upd8:
			return Costs[Goal] 
	else: 
		pc = Costs[Goal]
		for i in range(N):
			upd8 = True
			for s in range(N):
				for t,c in lines[s]:
					if c + Costs[s] < Costs[t]:
						Costs[t] = Costs[s]+c
						upd8 = True
			if not upd8: break

		if pc != Costs[Goal]:
			return -INF
		else:
			return Costs[Goal]

print(-BellmanFord(0,N-1))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N): 
		
		upd8 = False
		for s in range(N):
			
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					

		
		if not upd8:
			return Costs[Goal] 
	else: 
		pc = Costs[Goal]
		for i in range(N):
			upd8 = True
			for s in range(N):
				for t,c in lines[s]:
					if c + Costs[s] < Costs[t]:
						Costs[t] = Costs[s]+c
						upd8 = True
			if not upd8: break

		if pc != Costs[Goal]:
			return -INF
		else:
			return Costs[Goal]

print(-BellmanFord(0,N-1))

Solution (Python):
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(3000):
        update = False
        for e in edge:
            if (d[e[0]-1] != -inf and d[e[1]-1] < d[e[0]-1] + e[2]):
                d[e[1]-1] = d[e[0]-1] + e[2]
                update = True
                if (e[1] == n and i >= n):
                  return "inf"
        if not update:
            break
    return d[-1]
n,m = map(int,input().split())
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
ans = shortest_path(p,n,0)
print(ans)

Solution (Python):
class BellmanFord:
    INF = int(1e18)
    N = -1
    edge = []
    
    def __init__(self, N):
        self.N = N
        
    def add_edge(self, frm, to, cost):
        self.edge.append((frm, to, cost));
        
    def add_bi_edge(self, a, b, cost):
        self.add_edge(a, b, cost)
        self.add_edge(b, a, cost)
    
    def calcD(self, start):
        D = [self.INF] * self.N
        D[start] = 0
        update, cnt = True, 0
        flag = False
        while update:
            cnt = cnt + 1
            if cnt > self.N:
                return D if flag == False else 'NegativeCycle'
            update = False
            flag = False
            
            for frm, to, cost in self.edge:
                ncost = D[frm] + cost
                if D[frm] == self.INF or ncost >= D[to]:
                    continue
                D[to] = ncost
                update = True
                flag = flag | (to == self.N-1)
                
        return D

    
V, E = list(map(int, input().split()))
bf = BellmanFord(V)
for i in range(E):
    frm, to, cost = list(map(int, input().split()))
    bf.add_edge(frm - 1, to - 1, -cost)
    

ans = bf.calcD(0)
if ans == 'NegativeCycle':
    print("inf")
else:
    print(-ans[V-1])

Solution (Python):
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), -long(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    new_cost = dist_list[j] + edge[1]
                    if new_cost < dist_list[edge[0]]:
                        dist_list[edge[0]] = new_cost
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

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

def bf(links, n, st=1):
    inf = float('inf')
    dj = [-inf] * (n + 1)
    dj[st] = 0
    for _ in range(N):
        updated = False
        for link in links:
            fn, tn, lc = link
            if dj[fn] + lc > dj[tn]:
                dj[tn] = dj[fn] + lc
                updated = True
        if not updated: break
    else:
        negative = [False] * (n + 1)
        for _ in range(N):
            for link in links:
                fn, tn, lc = link
                negative[tn] |= negative[fn]
                if dj[fn] + lc > dj[tn]:
                    dj[tn] = dj[fn] + lc
                    negative[tn] = True
        if negative[N]: return inf
    return dj[-1]

links = []
for _ in range(M):
    links.append([int(x) for x in input().split()])

print(bf(links, N, 1))

Solution (Python):
import heapq
N, M = map(int, input().split())
E = [[] for i in range(N)]
revE = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, -c])
  revE[b - 1].append(a - 1)
revG = [False] * N
revG[-1] = True
Q = []
heapq.heappush(Q, N - 1)
while Q:
  s = heapq.heappop(Q)
  for adj in revE[s]:
    if not revG[adj]:
      revG[adj] = True
      heapq.heappush(Q, adj)
D = [N * 10 ** 9 + 1] * N
D[0] = 0
def bf(D):
  for i in range(N):
    _D = [d for d in D]
    for s in range(N):
      for adj in E[s]:
        _D[adj[0]] = min(D[s] + adj[1], _D[adj[0]])
    D = _D
  return D
D = bf(D)
D1 = [d for d in D]
D = bf(D)
for i in range(N):
  if revG[i] and D1[i] != D[i]:
    print('inf')
    break
else:
  print(-D[-1])

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

def bf(links, n, st=1):
    inf = float('inf')
    dj = [inf] * (n + 1)
    dj[st] = 0
    for i in range(N):
        updated = False
        for link in links:
            fn, tn, lc = link
            lc *= -1
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                updated = True
        if not updated: break
    else:
        pn = dj[-1]
        for i in range(N):
            updated = False
            for link in links:
                fn, tn, lc = link
                lc *= -1
                if dj[fn] + lc < dj[tn]:
                    dj[tn] = dj[fn] + lc
                    updated = True
            if not updated: break
        return inf if pn != dj[-1] else -dj[-1]
    return -dj[-1]

links = []
for _ in range(M):
    links.append([int(x) for x in input().split()])

print(bf(links, N, 1))

Solution (Python):
import heapq
N, M = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, -c])
D = [N * 10 ** 9 + 1] * N
D[0] = 0
def bf(D):
  for i in range(N):
    _D = [d for d in D]
    for s in range(N):
      for adj in E[s]:
        _D[adj[0]] = min(D[s] + adj[1], _D[adj[0]])
    D = _D
  return D
D = bf(D)
d1 = D[-1]
D = bf(D)
print(-d1 if d1 == D[-1] else 'inf')

Solution (Python):


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def BellmanFord(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    dist = defaultdict(lambda: sys.maxsize)
    pred = defaultdict(lambda: -1)

    dist[s] = 0

    N = len(V)
    for i in range(N+1):
        for u in g:
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    if i == N:
                        return 'inf'
                    dist[v] = dist[u] + g[u][v]
                    pred[v] = u
    return dist


@mt
def slv(N, M, ABC):
    g = defaultdict(dict)
    g_ = defaultdict(dict)
    for a, b, c in ABC:
        g_[b][a] = c

    reachable = [N]
    q = [N]
    while q:
        v = q.pop()
        for u in g_[v]:
            if u not in reachable:
                reachable.append(u)
                q.append(u)
    reachable = set(reachable)
    for a, b, c in ABC:
        if a in reachable and b in reachable:
            g[a][b] = -c

    dist = BellmanFord(g, 1)
    if dist == 'inf':
        return 'inf'
    return -1*dist[N]


def main():
    N, M = read_int_n()
    ABC = [read_int_n() for _ in range(M)]

    print(slv(N, M, ABC))


if __name__ == '__main__':
    main()

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

dist = [INF]*(n+1)
dist[1] = 0
for loop in range(n-1):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[-1]

negative = [False]*(n+1) 
for loop in range(n):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        if negative[a[i]] is True:
            negative[b[i]] = True

    if negative[-1] is True:
        break

if negative[-1] is True:
    print('inf')
else:
    print(-ans)

Solution (Python):
N, M = map(int, input().split())
paths = []

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
inf_flg = False 

for i in range(N * 2) :
    break_flg = True 
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c and not(cost[t] == cost[f] == INF):
            break_flg = False 
            cost[t] = cost[f] + c
            
            if i >= N and t == N - 1:
                inf_flg = True 
                break
        
    if break_flg == True :
            break
    
if inf_flg == True :
    print("inf")
else :
    for c in cost :
        if c == INF :
            print("")
    print(cost[N - 1])

Solution (Python):
N, M = map(int, input().split())
paths = []

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
break_flg, inf_flg = True, False
cnt = 0

for i in range(N) :
    break_flg = True 
    
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c :
            cost[t] = cost[f] + c
            break_flg = False
            
            if i == N - 1 and t == N - 1 :
                inf_flg = True 
            
    
    if break_flg == True :
        break
        
if inf_flg == True :
    print("inf")
else :
    print(cost[N - 1])

Solution (Python):
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), -long(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    new_cost = dist_list[j] + edge[1]
                    if new_cost < dist_list[edge[0]]:
                        dist_list[edge[0]] = new_cost
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, -long(c))]
        else:
            graph[a].append((b, -long(c)))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    new_cost = dist_list[j] + edge[1]
                    if new_cost < dist_list[edge[0]]:
                        dist_list[edge[0]] = new_cost
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), -long(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    
                    if dist_list[j] + edge[1] < dist_list[edge[0]]:
                        dist_list[edge[0]] = dist_list[j] + edge[1]
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), -long(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    new_cost = dist_list[j] + edge[1]
                    if new_cost < dist_list[edge[0]]:
                        dist_list[edge[0]] = new_cost
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

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

INF = 2 << 40
G, dist = [None for i in range(M)], [INF for j in range(N)]


class Edge:
    def __init__(self, f, t, cost):
        self.f = f
        self.t = t
        self.cost = cost


def bellman_ford(s):
    dist[s] = 0
    for i in range(2*N):
        for j in range(M):
            e = G[j]
            if dist[e.f] < INF and dist[e.f] + e.cost < dist[e.t]:
                dist[e.t] = dist[e.f] + e.cost

                if i >= N - 1 and (e.t == N - 1 or e.f == N - 1):
                    return True

    return False


def main():
    for i in range(M):
        a, b, c = map(int, input().split())
        G[i] = Edge(a-1, b-1, -c)

    c = bellman_ford(0)

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


if __name__ == '__main__':
    main()

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

g = [float("inf") for _ in range(0,n+1)]
g[1] = 0
negative = ["false" for _ in range(0,n+1)]

for i in range(0,n):
    for j in range(0,m):
        a,b,c = data[j]
        if g[a] != float("inf") and g[b] > g[a] + c:
            g[b] = g[a] + c
            if i == n-1:
                negative[b] = "true"
if negative[n] == "false":
    print(-g[n])
else:
    print("inf")

Solution (Python):
N, M = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]
C = [-float("inf")] * (N+1)
C[1] = 0
for i in range(N-1):
    for e in E:
        a, b, c = e
        C[b] = max(C[b], C[a]+c)
ans = C[N]
for i in range(N):
    for e in E:
        a, b, c = e
        C[b] = max(C[b], C[a]+c)
if C[N] == ans:
    print(ans)
else:
    print("inf")

Solution (Python):
def bellmanford(xyw, n, start):
    inf = float("inf")
    dist = [inf]*n
    dist[start] = 0

    for _ in range(n-1):
        for x,y,w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
    result = dist[n-1]
    negative = [0]*n
    for _ in range(n):
        for x, y, w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
                negative[y] = True
            if negative[x]:
                negative[y] = True
    return inf if negative[n-1] else -result


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

print(bellmanford(ABC, N, 0))