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):
N, M = map(int, input().split())
INF = float("inf")

start = []
end = []
weight = []
node_cost = [-INF] * N
for _ in range(M):
    a, b, c = map(int, input().split())
    start.append(a - 1)
    end.append(b - 1)
    weight.append(c)

node_cost[0] = 0
for _ in range(N - 1):
    for i in range(M):
        new_cost = node_cost[start[i]] + weight[i]
        if new_cost > node_cost[end[i]]:
            node_cost[end[i]] = new_cost
ans = node_cost[N-1]
cycle = [False] * N
for _ in range(N):
    for i in range(M):
        if cycle[start[i]]:
            cycle[end[i]] = True
        new_cost = node_cost[start[i]] + weight[i]
        if new_cost > node_cost[end[i]]:
            cycle[end[i]] = True
if cycle[N-1]:
    ans = "inf"
print(ans)

Solution (Python):
import sys
class DSU:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), self.leader(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]

    def groups(self):
        leader_buf = [self.leader(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[leader_buf[i]].append(i)
        return [r for r in result if r != []]

class Fenwick_Tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n

    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s
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 -d[n-1]
N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)

Solution (Python):
def bellman_ford(a, v, e):
    inf = pow(2, 61) - 1
    dist = [inf] * v
    dist[a] = 0
    for i in range(2 * v):
        f = 0
        for s, t, d in E:
            if not dist[s] == inf and dist[t] > dist[s] + d:
                dist[t] = dist[s] + d
                f = 1
        if not f:
            x0 = dist[-1]
            break
        elif f and i == v - 1:
            x0 = dist[-1]
    if x0 == dist[-1]:
        return -dist[-1]
    else:
        return "inf"

n, m = map(int, input().split())
E = []
for _ in range(m):
    a, b, c = map(int, input().split())
    E.append([a - 1, b - 1, -c])
ans = bellman_ford(0, n, m)
print(ans)

Solution (Python):
n,m=map(int,input().split())
abc=[tuple(map(int,input().split())) for _ in range(m)]
Inf=float('inf')
dist=[Inf]*n
dist[0]=0
for i in range(n):
    for a,b,c in abc:
        a,b,c=a-1,b-1,-c
        if dist[b] >dist[a]+c:
            dist[b]=dist[a]+c
            if i==n-1 and b==n-1:
                print('inf')
                exit()
print(-dist[-1])

Solution (Python):
def BellmanFord(start):
    
    inf = float("inf")
    dist = [inf] * N
    dist[start] = 0
    
    for i in range(N):
        update = False
        for x, y, z in G:
            if dist[y] > dist[x] + z:
                dist[y] = dist[x] + z
                update = True
                
                
                if y == N - 1 and i == N - 1:
                    return "inf"

        if update is False:
            break
        
    return -dist[-1]

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

d = BellmanFord(0)
print(d)

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









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

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

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

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    
    
    
    cnt = 0
    while True:
        update = False
        
        for e in es:
            
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
                if cnt == n-1 and e.end == n-1:
                  print('inf')
                  sys.exit()
        cnt += 1
        
        if not update or cnt == n:
            break
    return dist

es = []

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


print(-bellman_ford(N, es,0)[N-1])

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

class Bellman_Ford:
    def __init__(self, v=None, e=None, lis=None, start=None, end=None, inf=pow(10, 18)):
        self.V = v
        self.E = e
        self.lis = lis
        self.start = start if start else 0
        self.end = end if end else self.V-1
        self.inf = inf
        self.close_minus = False
        self.count = self.V*2-1
        self.negative = [False]*self.V
        self.judge = False

    """
    リストは各要素が(始点、終点、重み)となる有向辺の集合とする(無向なら両方作る必要あり)
    Vは頂点数、Eは辺の数（これは今の所使われない）
    close_minusがTrueなら、負の閉路が存在してしまうので、注意する
    """

    def getlist(self, lis):
        self.lis = lis
    
    def def_start(self, s):
        self.start = s
    
    def def_end(self, e):
        self.end = e

    def def_inf(self, inf):
        self.inf = inf
    
    def def_vertice(self, v):
        self.V = v
    
    def def_edge(self, e):
        self.E = e
    
    def prepare(self):
        self.cost = [self.inf]*self.V 
        self.cost[self.start] = 0 

    def search(self):
        for i in range(self.V):
            update = False 
            for x, y, z in self.lis:
                if self.cost[y] > self.cost[x] + z:
                    self.cost[y] = self.cost[x] + z
                    update = True
                    if self.count <= self.V:
                        self.negative[y] = True
                    self.count -= 1
                if self.count == self.V:
                    self.judge = True
                if self.count == 0:
                    break
            if not update or not self.count:
                break
            
            if i == self.V - 1:
                self.close_minus = True
                return False
        return True

    def main(self):
        self.prepare()
        self.search()
    
    def cost_all(self):
        return self.cost

def main():
    n, m = map(int,input().split())
    arrange = [None]*m

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

    bf = Bellman_Ford(v=n, e=m, lis=arrange)
    bf.main()

    for a, b, c in arrange:
        if bf.negative[a]:
            bf.negative[b] = True

    if bf.negative[n-1]:
        print("inf")
    else:
        print(-bf.cost[-1]) 


if __name__ == "__main__":
    main()

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

def bellman_ford(s):
    d = [float('inf')]*n 
    d[s] = 0 
    flg = False
    for i in range(n):
        update = False 
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            inf_flg = d[-1]
            flg = True
    if flg:
        for i in range(n):
            update = False 
            for x, y, z in g:
                if d[y] > d[x] + z:
                    d[y] = d[x] + z
                    update = True
            if not update:
                break
            if i == n - 1:
                if inf_flg != d[-1]:
                    return "inf"
    return -1 * d[-1]

print(bellman_ford(0))

Solution (Python):
INF = -float('inf')
 
def bellmanford(n,e,r):
  costs = [INF]*n
  costs[r] = 0
  for i in range(n):
    for u,v,c in e:
      if costs[u]+c > costs[v] and costs[u]!=INF:
        costs[v] = costs[u]+c
        if i==n-1 and v==n-1:
          return 'inf'
  return costs[n-1]
 
n,m = map(int, input().split())
edge = []
for i in range(m):
  a,b,t = map(int, input().split())
  edge.append((a-1,b-1,t))
 
print(bellmanford(n,edge,0))

Solution (Python):
from collections import deque
N,M = map(int,input().split())

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

def dfs(X,s):
    used = {s}
    search = deque([s])
    while search:
        ss = search.pop()
        for sss in X[ss]:
            if sss in used:
                continue
            used.add(sss)
            search.append(sss)
    return used

U = dfs(Adake,0) & dfs(Bdake,N-1)
ABC = [(a,b,c) for (a,b,c) in ABC if a in U and b in U]

INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for a,b,c in ABC:
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i==N-1 and b == N-1:
                print('inf')
                exit()
print(-dist[-1])

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

INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for a,b,c in ABC:
        a,b,c = a-1,b-1,-c
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i==N-1 and b == N-1:
                print('inf')
                exit()
print(-dist[-1])

Solution (Python):
import sys
N,M = map(int, input().split())
abc = [[] for _ in range(N)]
for i in range(M):
    a,b,c = map(int, input().split())
    abc[a-1].append((b-1,c))
    
S = [-float("inf")]*N
S[0] = 0
T = [0]
m = 0
n = 0
j = False
while T:
    t = T.pop(0)
    m += 1
    for tb,tc in abc[t]:
        if S[tb] < S[t]+tc:
            S[tb] = S[t]+tc
            T.append(tb)
    if m > M+1:
        d = abc[tb]
        if N-1 in list(d[i][0] for i in range(len(d))):
            j = True
        n += 1
    if n > M:
        if j:
            print("inf")
            sys.exit()
        else:
            break

print(S[-1])

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

INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for a,b,c in ABC:
        a,b,c = a-1,b-1,-c
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i==N-1 and b == N-1:
                print('inf')
                exit()
print(-dist[-1])

Solution (Python):

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

def BellmanFord(n,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      
      
      negative=[False]*n
      for i in range(n):
        for p,q,r in es:
          if d[q]<d[p]+r:
            negative[q]=True
            d[q]=d[p]+r
      if negative[n-1]==True:
        print("inf")
        exit()
      else:
        print(d[n-1])
        exit()
        
  print(d[n-1])
  
  
  
BellmanFord(n,0,es)

Solution (Python):

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

def BellmanFord(n,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      
      
      negative=[False]*n
      for i in range(n):
        for p,q,r in es:
          if d[q]<d[p]+r:
            negative[q]=True
            d[q]=d[p]+r
      if negative[n-1]==True:
        print("inf")
        exit()
      else:
        print(d[n-1])
        exit()
        
  print(d[n-1])
  
  
  
BellmanFord(n,0,es)

Solution (Python):
def cin():  return list(map(int,input().split()))

def bellman_ford(s):
    d = [float('inf')] * N
    d[s] = 0
    for i in range(N):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                if i == N - 1 and y == N - 1:  return "inf"
    return -d[N - 1]

N, M = cin()
G = []
bfr = []
for i in range(M):
    s, t, w = cin()
    G.append((s - 1, t - 1, -w))
ans = bellman_ford(0)
print(ans)

Solution (Python):
class Edge:

    def __init__(self, origin, to, cost):
        self.origin = origin
        self.to = to
        self.cost = cost

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

edges = [None] * M

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



dist = [float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != float("inf") and dist[e.to] > dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    i += 1

    if not isUpdated:
        break

    if i == N-1:
        break





isUpdated = [False for _ in range(N)]
for i in range(N):
    for e in edges:
        if dist[e.to] > dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated[e.to] = True


if isUpdated[N-1]:
    print("inf")

else:
    print(-dist[N-1])

Solution (Python):
n, m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(m)]
v = [-(10 ** 9 * 2000)] * n


v[0] = 0
for i in range(n):
    tmp = v[-1]
    for a, b, cost in e:
        if v[a-1] + cost > v[b-1]:
            v[b-1] = v[a-1] + cost
    if tmp != v[-1] and i == n-1: break        
else:
    print(v[n-1])
    exit()

print("inf")

Solution (Python):
'''
    [bellman_ford]
'''
def bellman_ford(s, n, g): 
    INF = 10**18
    d = [INF]*n
    d[s] = 0
    for i in range(n-1): 
        update = False
        for v_from, v_to, cost in g:
            if d[v_to] > d[v_from] + cost:
                d[v_to] = d[v_from] + cost
                update = True
        if not update:
            return d
    return d
    
    
    


def bellman_ford2(s, n, g, d): 
    INF = 10**18
    
    
    for i in range(n-1): 
        update = False
        for v_from, v_to, cost in g:
            if d[v_to] > d[v_from] + cost:
                d[v_to] = -INF
    return d


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

d = bellman_ford(0,n,g)
d2 = bellman_ford2(0,n,g,d[:])

INF = 10**18
if d2[n-1] <= -INF:
    print('inf')
else:
    print(-d[n-1])

Solution (Python):


n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  negative=[False]*n
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
        if cnt==n-1:
          negative[q]=True
    if cnt==n-1:
      for count in range(n):
        for p,q,r in es:
          if negative[p]:
            negative[q]=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      if negative[n-1]:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
        
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Solution (Python):


n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  negative=[False]*n
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
        if cnt==n-1:
          negative[q]=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      if negative[n-1]:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
        
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Solution (Python):


n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n-1:
      memo=d[n-1]
    if cnt==n+1:
      
      if d[n-1]>memo:
        print(float("INF"))
        sys.exit()
      else:
        print(memo)
        sys.exit()
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Solution (Python):


n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n-1:
      memo=d[n-1]
    if cnt==n+1:
      
      if d[n-1]>memo:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Solution (Python):


n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n-1:
      memo=d[n-1]
    if cnt==n:
      
      if d[n-1]>memo:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Solution (Python):
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright





n,m=map(int,input().split()) 
G=[] ; Y=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G.append([a,b,-w])








if 1:
    ansdist=[inf for i in range(n)]
    ansdist[0]=0
    for i in range(n-1):
        for edge in G:
            a,b,d=edge
            
            if ansdist[b] > ansdist[a]+d:  
                ansdist[b]= ansdist[a]+d
                

    

ans=-ansdist[-1]
neg=[0]*n
for i in range(n):
    for edge in G:
        a,b,d=edge
        if ansdist[b]>ansdist[a]+d:
            ansdist[b] = ansdist[a]+d
            neg[b]=1
        if neg[a]:neg[b]=1
if neg[-1]:
    print("inf")
else:
    print(ans)

Solution (Python):
def bellman_ford(n, s, edges, init_val = float('inf')): 
    d = [init_val] * n
    d[s] = 0
    for _ in range(n):
        updated = False
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = d[vf] + w
                updated = True
        if not updated:
            break
    while updated: 
        updated = False
        for vf, vt, w in edges:
            if d[vt] > d[vf] + w:
                d[vt] = -float('inf')
                updated = True
    return d

n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1,b-1,-w))
d = bellman_ford(n, 0, edges)
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Solution (Python):
from collections import deque

def fast_bellman_ford(n, s, graph, edge_n, init_val): 
    d = [init_val] * n
    d[s] = 0
    q = deque([s])
    checker = [-1] * n
    for i in range(n):
        m = len(q)
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    if checker[vt] < i:
                        q.append(vt)
                        checker[vt] = i
        if not q:
            break
    if q: 
        minus_inf = -float('inf')
        i += 1
        while q:
            m = len(q)
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        if checker[vt] < i:
                            q.append(vt)
                            checker[vt] = i
            i += 1
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Solution (Python):
class PreallocatedQueue:
    def __init__(self, n, init_val):
        self.queue = [init_val] * n 
        self.l = 0
        self.r = 0
        self.n = n
        self.init_val = init_val
        self.count = 0

    def append(self, val):
        if self.count == self.n:
            if self.r == 0:
                self.queue = self.queue + [self.init_val] * self.n
            else:
                self.queue = self.queue[self.l:] + self.queue[:self.r] + [self.init_val] * self.n
                self.l = 0
            self.r = self.n
            self.n *= 2
        self.queue[self.r] = val
        self.r = (self.r + 1) % self.n
        self.count += 1

    def popleft(self):
        if self.count == 0:
            raise IndexError('popleft from empty queue')
        val = self.queue[self.l]
        self.l = (self.l + 1) % self.n
        self.count -= 1
        return val

    def pop(self):
        if self.count == 0:
            raise IndexError('pop from empty queue')
        val = self.queue[self.r - 1]
        self.r = (self.r - 1) % self.n
        self.count -= 1
        return val
    
    def size(self):
        return self.count
    
    def __bool__(self):
        return self.count != 0

def fast_bellman_ford(n, s, graph, edge_n, init_val): 
    d = [init_val] * n
    d[s] = 0
    q = PreallocatedQueue(edge_n, 0)
    q.append(s)
    checker = [-1] * n
    for i in range(n):
        m = q.count
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    if checker[vt] < i:
                        q.append(vt)
                        checker[vt] = i
        if not q:
            break
    if q: 
        minus_inf = -float('inf')
        i += 1
        while q:
            m = q.count
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        if checker[vt] < i:
                            q.append(vt)
                            checker[vt] = i
            i += 1
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Solution (Python):
def fast_bellman_ford(n, s, graph, init_val): 
    d = [init_val] * n
    d[s] = 0
    from_set = {s}
    for _ in range(n):
        next_set = set()
        for vf in from_set:
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    next_set.add(vt)
        from_set = next_set
        if not from_set:
            break
    if from_set: 
        while from_set:
            minus_inf = -float('inf')
            next_set = set()
            for vf in from_set:
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        next_set.add(vt)
            from_set = next_set
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Solution (Python):
def bellman_ford(n, s, edges, init_val = float('inf')): 
    d = [init_val] * n
    d[s] = 0
    for _ in range(n):
        updated = False
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = d[vf] + w
                updated = True
        if not updated:
            break
    while updated: 
        updated = False
        for vf, vt, w in edges:
            if d[vt] > d[vf] + w:
                d[vt] = -float('inf')
                updated = True
    return d

n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1,b-1,-w))
d = bellman_ford(n, 0, edges)
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Solution (Python):
def bellman_ford(n, s, edges, init_val): 
    d = [init_val] * n
    d[0] = 0
    for _ in range(n):
        updated = False
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = d[vf] + w
                updated = True
        if not updated:
            break
    if updated: 
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = -float('inf')
    return d

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

edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1, b-1, -w))
d = bellman_ford(n, 0, edges, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Solution (Python):
class BellmanFord:
    def __init__(self, n, init_val = float('inf')):
        self.d = [init_val] * n 
        self.init_val = init_val

    def shortest_path(self, s, edges):
        self.d[s] = 0
        for _ in range(n):
            updated = False
            for a, b, w in edges:
                if self.d[a] != self.init_val and self.d[b] > self.d[a] + w:
                    self.d[b] = self.d[a] + w
                    updated = True
            if not updated:
                break
        if updated: 
            for a, b, w in edges:
                if self.d[a] != self.init_val and self.d[b] > self.d[a] + w:
                    self.d[b] = -float('inf')
    
    def get_path_length(self, i):
        return self.d[i]

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

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

bf = BellmanFord(n)
bf.shortest_path(0, edges)
ans = bf.get_path_length(n-1)
print(-ans if ans != -float('inf') else 'inf')

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

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

init_val = -10 ** 9 * 1000
d = [init_val] * n
d[0] = 0
for _ in range(n):
    updated = False
    for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            updated = True
    if not updated:
        break
if updated: 
     for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            if b == n - 1:
                print('inf')
                quit()
print(d[n-1])