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-----
3 3
1 2 4
2 3 3
1 3 5

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
n, m = map( int, input().split() )
edge_list = []
for _ in range( m ):
    a_i, b_i, c_i = map( int, input().split() )
    edge_list.append( ( a_i - 1, b_i - 1, - c_i ) )

INF = float("inf")
cost = [ INF ] * n
cost[ 0 ] = 0

NegativeLoopExist = False
for i in range( n ):
    for j in range( m ):
        a, b, c = edge_list[ j ]
        if cost[ a ] != INF and cost[ b ] > cost[ a ] + c:
            cost[ b ] = cost[ a ] + c
            if i == n - 1 and b == n - 1:
                NegativeLoopExist = True

if NegativeLoopExist:
    print( "inf" )
else:
    print( - cost[ n - 1 ] )

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

INF = float('inf')

def find_negative_loop(n,es,s):
    #負の経路の検出
    #n:頂点数, es[i]: [辺の始点,辺の終点,辺のコスト], s:始点
    dist = [-INF] * n
    dist[s] = 0

    for i in range(n):
        for a,b,c in es:
            if dist[b] < dist[a]+c:
                dist[b] = dist[a]+c
                # if i == n-1: # n回目にも更新が行われている場合，ループが存在する
                if i == n-1 and b==n-1: # 終点に影響を及ぼすループが存在する
                        return INF
    return dist[n-1]

ans = find_negative_loop(n,es,0)

if ans == INF:
    print('inf')
    return

print(ans)


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')
                return
print(-dist[-1])

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 = list(map(int, input().split()))
edge = []
for i in range(m):
  a,b,t = list(map(int, input().split()))
  edge.append((a-1,b-1,t))

print((bellmanford(n,edge,0)))


import sys
INF=float('inf')
def Bellmanford(n,edges,r):
  d=[INF]*n
  d[r]=0    
  for i in range(n):
    for (u,v,c) in edges:
      if d[u]!=INF and d[u]+c<d[v]:
        d[v]=d[u]+c
        if i==n-1 and v==n-1:
          return 'inf'   
  return (-1)*d[n-1]

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

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


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

dist = [float('inf')]*n
dist[0] = 0
for i in range(n-1):
    # n-1回ループすることで、到達できるすべての頂点の更新ができる
    for st, en , score in edges:
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score

negative = [False] * n

for loop in range(n):
    # n回目以降のループで更新された頂点は負閉路を含む
    # それをn回繰り返して更新された頂点は、負閉路の影響を受けている
    for e in edges:
        st, en, score = e
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score
            negative[en] = True
        if negative[st]:
            negative[en] = True

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

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

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

for i in range(N):
    update = False
    for a,b,c in abc:
        a,b = a-1,b-1
        if cost[a] != -(10**10)*N:
            if cost[b] < cost[a] + c:
                cost[b] = cost[a] + c
                update = True
    if i == 0:
        Max = cost[N-1]
    elif i < N-1:
        Max = max(Max,cost[N-1])


if update == True and Max < cost[N-1]:
    print('inf')
else:
    print(Max)


import bisect
import collections
import sys

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


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


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


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


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

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

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


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)
bf.fill_cost()
negative_loops = bf.fill_cost(check=True)
# print(negative_loops, bf.cost)
if N - 1 in negative_loops:
    print('inf')
else:
    print((-bf.cost[-1]))


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

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

INF = 10**15
d = [INF] * N
d[0] = 0
def bellman_ford():
  nonlocal d
  for i in range(N):
    for a, b, c in road:
      d[b] = min(d[b], d[a] + c)

bellman_ford()
for a, b, c in road:
  new_d = d[a] + c
  if new_d < d[b]:
    d[b] = - float('inf')

bellman_ford()
if d[-1] > -float('inf'):
  print(int(-d[-1]))
else:
  print('inf')

n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
node=[-float('inf') for i in range(n+1)]
node[1]=0
inf=False
for i in range(2*n+1):
  loop=False
  for s,e,c in edge:
    if node[e]<node[s]+c:
      node[e]=node[s]+c
      if e==n:
        loop=True
  if i>=n and loop:
    inf=True
    break
if inf:
  print('inf')
else:
  print(node[-1])

import sys

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


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


def __starting_point():
    solve()

__starting_point()

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    # 注意点として、閉路を探索(=スコアが更新されたか確かめる)ためにn*2回実行する必要がある
    for i in range(n*2):
        for edge in g:
            if edge[0] != float('inf') and d[edge[1]] > d[edge[0]] + edge[2]:
                d[edge[1]] = d[edge[0]] + edge[2]
                if i>=n-1 and edge[1] == n-1:
                    return -1
    return d

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

ret = bellman_ford(0)

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



from scipy.sparse.csgraph import connected_components, bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix

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

# N-1→0の辺を追加してから卿連結判定⇒ゴールにたどり着けない閉路を除外
connect_check = csr_matrix(([1] * (M + 1), (frm + [N - 1], to + [0])), shape=(N, N))
_, labels = connected_components(connect_check, connection='strong')
label_num = labels[0]
frm_c, to_c, length_c = [], [], []
for i in range(M):
    if labels[frm[i]] == labels[to[i]] == label_num:
        frm_c.append(frm[i])
        to_c.append(to[i])
        length_c.append(length[i])

matr = csr_matrix((length_c, (frm_c, to_c)), shape=(N, N))

try:
    ans = -int(bellman_ford(matr, indices=0)[N - 1])
    print(ans)
except NegativeCycleError:
    print('inf')


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

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

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            # ワーシャルフロイド法の性質より、N回目に更新があるならinf
            if i == N - 1 and nn == N:
                print("inf")
                return
            cost[nn] = cost[n] + c

print(cost[N])

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

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

print((main()))


import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
node=[-float('inf') for i in range(n+1)]
node[1]=0
inf=False
for i in range(2*n+1):
  change=False
  for s,e,c in edge:
    if node[e]<node[s]+c:
      node[e]=node[s]+c
      if e==n:
        change=True
  if i>=n and change:
    inf=True
if inf:
  print('inf')
else:
  print(node[-1])

def bellman_ford():#ﾌﾍｲﾛ検出
    n,m=list(map(int, input().split()))
    g = [[] for _ in range(n)]
    for i in range(m):
        a,b,c=list(map(int, input().split()))
        g[a-1].append([b-1,-1*c])
    dist = [float("inf")]*n
    inf = float("inf")
    dist[0] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(g[v])):
                edge = g[v][k]
                if(dist[v]!=inf and dist[v]+edge[1] < dist[edge[0]]):#dist[v]!=10000:未到達だったら無視するので
                    dist[edge[0]] = dist[v] + edge[1]

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

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



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

    return False


def main():
    bellman_ford()
def __starting_point():
    main()

__starting_point()

import sys

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


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


def __starting_point():
    solve()

__starting_point()

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

for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -cost))
    E[to].append(fr)

def canGo():
    st = [N - 1]
    visited = [False] * N
    visited[N - 1] = True
    while st:
        for to in E[st.pop()]:
            if visited[to]:
                continue
            visited[to] = True
            st.append(to)
    return visited

V = canGo()

minDist = [float('inf')] * N
minDist[0] = 0

for i in range(N + 1):
    for fr, to, cost in edges:
        d = minDist[fr] + cost
        if minDist[to] > d:
            if i == N and V[to]:
                print('inf')
                return
            minDist[to] = d

print(-minDist[N - 1])

import queue
def bfs(G, s):
    st = set()
    q = queue.Queue()
    st.add(s)
    q.put(s)
    while not q.empty():
        p = q.get()
        for v, _ in G[p]:
            if not v in st:
                st.add(v)
                q.put(v)
    return st

def solve(G, st):
    n = len(G)
    score = [-float("inf")]*n
    score[0] = 0
    for i in range(n):
        f = True
        for s in range(n):
            for t, u in G[s]:
                if not s in st or not t in st:
                    continue
                if score[t] < score[s] + u:
                    f = False
                    score[t] = score[s] + u
        if f:
            break
        if i == n-1:
            return "inf"
    return score[n-1]

def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n)]
    revG = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        a, b = a-1, b-1
        G[a].append([b, c])
        revG[b].append([a, c])
    st1 = bfs(G, 0)
    st2 = bfs(revG, n-1)
    st = st1 & st2
    print(solve(G, st))

def __starting_point():
    main()
__starting_point()

# solution
import io

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

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

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

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

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

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

N, M = map(int, input().split())
edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append([a, b, -c])
def bellman_ford(edges, N):
    dist = [float('inf') for i in range(N)]
    dist[0] = 0
    for i in range(N-1):
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
    negative = [False] * N

    for i in range(N):
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                negative[edge[1] - 1] = True
            if negative[edge[0] - 1] == True:
                negative[edge[1] - 1] =True
    
    return 'inf' if negative[-1] else -dist[-1]

print(bellman_ford(edges, N))

import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(s,u):
  if u==N:
    reachable_list[s]=True
    return True
  
  visited[u]=True
  for v in graph[u]:
    if not visited[v]:
      check_reachable(s,v)    
  return False

reachable_list=[False]*(N+1)
for i in range(1,N+1):
  visited=[False]*(N+1)
  check_reachable(i,i)
#print(reachable_list)
  
elist2=[]
for a,b,nc in elist:
  if reachable_list[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

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

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

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(m)]
dist = [-float("inf")]*(n+1)
dist[1] = 0
for i in range(n):
  for a, b, c in ABC:
    if dist[b] < dist[a]+c:
      if i == n-1 and b == n:
        print("inf")
        return
      dist[b] = dist[a]+c
ans = dist[n]
print(ans)

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')
                return
print(-dist[-1])

n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
check=[False for i in range(n+1)]
inf=False
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n-1):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      check[e]=True
    if check[s]:
      check[e]=True
if check[-1]:
  print('inf')
else:
  print(-node[-1])

n, m = map( int, input().split() )
edge_list = []
for _ in range( m ):
    a_i, b_i, c_i = map( int, input().split() )
    edge_list.append( ( a_i - 1, b_i - 1, - c_i ) )

INF = 10 ** 15
cost = [ INF ] * n
cost[ 0 ] = 0

NegativeLoopExist = False
for i in range( n ):
    for j in range( m ):
        a, b, c = edge_list[ j ]
        if cost[ a ] != INF and cost[ b ] > cost[ a ] + c:
            cost[ b ] = cost[ a ] + c
            if i == n - 1 and b == n - 1 :
                NegativeLoopExist = True

if NegativeLoopExist:
    print( "inf" )
else:
    print( - cost[ n - 1 ] )

import sys
rl=sys.stdin.readline

def main():
    n,m=list(map(int,rl().strip().split()))
    eaw=[list(map(int,rl().strip().split())) for _ in range(m)]
    d=dict(((x[0]-1,x[1]-1),-x[2]) for x in eaw)
    inf=10**14
    mdl=[inf]*n
    mdl[0]=0
    def blrelax(dl,k):
        for _ in range(k):
            for e in iter(d):
                if dl[e[0]]+d[e]<dl[e[1]]:
                    dl[e[1]]=dl[e[0]]+d[e]
    blrelax(mdl,n-1)
    a1=mdl[n-1]
    blrelax(mdl,n)
    a2=mdl[n-1]
    if a1>a2:
        print('inf')
    else:
        print((-a1))
    
def __starting_point():
    main()

__starting_point()

def Bellman_Ford(s, g, inf=1 << 60):
    # https://tjkendev.github.io/procon-library/python/graph/bellman-ford.html
    N = len(g)
    dist = [inf] * N
    dist[s] = 0

    for _ in range(N):
        not_updated = True
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c
                not_updated = False
        if not_updated: break

    else:
        # 負閉路が存在する
        ret = dist[N - 1]
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c

        if ret == dist[N - 1]:
            return -ret
        else:
            return 'inf'

    return -dist[N - 1]


def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        g[a].add((b, -c))

    ans = Bellman_Ford(s=0, g=g)
    print(ans)


def __starting_point():
    main()

__starting_point()

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

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

d = [float("inf") for _ in range(n)]
d[0] = 0

check = [0 for _ in range(n)]

for i in range(n):
    for now, next, weight in edge:
        if d[next] > d[now] + weight:
            d[next] = d[now] + weight
            if i == n-1:
                check[next] = 1
        if i == n-1:
            if check[now]:
                check[next] = 1

if check[-1]:
    print("inf")
else:
    print(-d[-1])

n,m=map(int,input().split(' '))
piece=[0]*m
for i in range(m):
    piece[i]=tuple(map(int,input().split(' ')))

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

for v in range(n-1):
    for e in range(m):
        a,b,c=piece[e]
        if node[b-1] > node[a-1]-c:
            node[b-1] = node[a-1]-c
ans=node[n-1]
for e in range(m):
    a,b,c=piece[e]
    if node[b-1] > node[a-1] - c:
        node[b-1] = node[a-1] -c

if ans != node[n-1]:
    print('inf')
else:
    print(-ans)

N,M,*L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
rdic = [[] for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dic[a].append(b)
  rdic[b].append(a)

ok1 = [False]*(N+1)
ok1[1] = True
q = [1]
while q:
  p = q.pop()
  for v in dic[p]:
    if not ok1[v]:
      ok1[v] = True
      q.append(v)
ok2 = [False]*(N+1)
ok2[N] = True
q = [N]
while q:
  p = q.pop()
  for v in rdic[p]:
    if not ok2[v]:
      ok2[v] = True
      q.append(v)
ok = [a&b for a,b in zip(ok1,ok2)]
cnt = 0
dist = [-10**20]*(N+1)
dist[1] = 0
while True:
  flag = True
  for a,b,c in zip(*[iter(L)]*3):
    if ok[a]&ok[b] and ok[a]!=-10**20 and dist[b]<dist[a]+c:
      flag = False
      dist[b] = dist[a]+c
  if flag:
    print(dist[N])
    break
  cnt += 1
  if cnt>N:
    print('inf')
    break

import sys
input = sys.stdin.readline

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

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

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

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

    return costs

main()

def solve(V,E,r,edges):
    cost=[-float('inf')]*V
    cost[r]=0
    for _ in range(V-1):
        for edge in edges:
            s=edge[0]
            t=edge[1]
            d=edge[2]
            if cost[t]<cost[s]+d:
                cost[t]=cost[s]+d
    ans=cost[V-1]
    for _ in range(V-1):
        for edge in edges:
            s=edge[0]
            t=edge[1]
            d=edge[2]
            if cost[t]<cost[s]+d:
                cost[t]=cost[s]+d
    if ans!=cost[V-1]:
        return float('inf')
    return ans
            



V,E=map(int,input().split())
edges=[]
for _ in range(E):
    s,t,d=map(int,input().split())
    s-=1
    t-=1
    edges.append(tuple((s,t,d)))
ans=solve(V,E,0,edges)
if ans==float('inf'):
    print("inf")
else:
    print(ans)

N, M = map(int, input().split())
inf = 10**18
edges = []

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

dist = [inf]*N
dist[0] = 0
update = False
for i in range(N):
    for a, b, c in edges:
        if dist[b]>dist[a]+c:
            dist[b] = dist[a]+c
            if b==N-1 and i==N-1:
                update = True

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

n, m = map(int, input().split())
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))
for i in range(n):
    for a, b, c in edge:
        if dist[a]!=NINF and dist[b] < dist[a] + c:
            dist[b] = dist[a] + c
            if i==n-1 and b==n-1:
                print('inf')
                return
print(dist[-1])

def BellmanFord():
    def BF(s, n, edge, inf=float("inf")):
        d = [inf for i in range(n)]
        d[s] = 0
        for i in range(n):
            for before, after, dist in edge:
                if before != inf:
                    d[after] = min(d[after], d[before] + dist)
            if i == n - 2:
                t = d[:]
            elif i == n - 1:
                for i, j in enumerate(d):
                    if j != t[i]:
                        d[i] = -inf
        return list(map(lambda x: -x, d))
    n, m = map(int, input().split())
    inf = 10 ** 20
    edge = [list(map(int, input().split())) for i in range(m)]
    edge = [[x - 1, y - 1, -z] for x, y, z in edge]
    l = BF(0, n, edge)
    print(l[-1] if l[-1] < inf else "inf")
BellmanFord()

import sys
INF = float("inf")


def Bellmanford(n, edges, r):  # 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)

N, M = map(int, input().split())
edges = [None]*M
INF = 10**18

for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a-1, b-1, -c)
    
def bellman(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[-1]
    
ans = bellman(N, edges, 0)
print(ans)

#負の経路の検出
def find_negative_loop(n, es, d):
    #始点はどこでもよい
    check = [0 for _ in range(n)]
    for _ in range(n):
        for p, q, r in es:
            #e: 辺iについて
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                check[q] = True
            if check[p]:
                check[q] = True
                # if i == n-1:
                #     return True
    return check

def shortest_path(s, n, es):
    #s -> i　の最短経路
    #s: 始点、n: 頂点数、w:辺の数、es[i]: [辺の始点、辺の終点、辺のコスト]
    d = [float("inf")] * n
    #d[i]: s->iの最短距離
    d[s] = 0
    for _ in range(n):
        update = False
        for p, q, r in es:
            #e: 辺iについて
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        # print(update)
        if not update:
            break
    return d

n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [] #es[i]: [辺の始点,辺の終点,辺のコスト]

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

# print(shortest_path(0, n, es))
# print(es)

# if find_negative_loop(n,es):

d = shortest_path(0, n, es)

# print(d)

c = find_negative_loop(n, es, d)
# print(c)



if c[-1]:
    print("inf")
else:
    # d = shortest_path(0, n, es)
    print(-d[-1])

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

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

def __starting_point():
    main()
__starting_point()

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')
                return
print(-dist[-1])

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

cost = [-(10**10)*N]*N
cost[0] = 0

for i in range(N):
    update = False
    for a,b,c in abc:
        a,b = a-1,b-1
        if cost[a] != -(10**10)*N:
            if cost[b] < cost[a] + c:
                cost[b] = cost[a] + c
                update = True
    if i == 0:
        Max = cost[N-1]
    elif i < N-1:
        Max = max(Max,cost[N-1])


if update == True and Max < cost[N-1]:
    print('inf')
else:
    print(Max)


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

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

for i in range(2):
    for a,b,c in abc:
        a,b = a-1,b-1
        cost[b] = max(cost[b], cost[a] + c)

    if i == 0:
        ans = cost[N-1]
    else:
        Max = cost[N-1]


if ans != Max:
    print('inf')
else:
    print(ans)


INF = -float("inf")

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

    for i in range(n):  # たかだかn-1回ループ　n回目でまだ更新できたら負閉路がある
        for u, v, c in edges:
            if dp[u] != INF and dp[u] + c > dp[v]:
                dp[v] = dp[u] + c
                if i == n-1 and v == n-1:
                    return "inf"

    return dp[n-1]


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

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

ans = Bellmanford(N, E)

print(ans)

import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[False]*(N+1)
for i in range(1,N+1):
  if not reachable[i]:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

import sys


def input():
    return sys.stdin.readline().strip()


def bellman_ford(edges, N, start):
    dist = [float("inf") for _ in range(N)]
    dist[start] = 0
    # 辺の情報を見ることを1ループとすると
    # 1回のループで,最低でも1つの頂点について，スタートからの最短距離が求まる
    # つまり,スタートからの全ての頂点への距離は，
    # スタートを除いた頂点の数である,(N-1)回のループで求まる．
    for i in range(2 * N):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] - cost:
                dist[to] = dist[fro] - cost
                # N回目に頂点の更新があると，負の経路がある
                if i == N - 1:
                    dist[to] = -float("inf")
    return dist


def main():
    N, M = list(map(int, input().split()))
    edge = []
    for i in range(M):
        a, b, c = list(map(int, input().split()))
        edge.append((a - 1, b - 1, c))
    D = bellman_ford(edge, N, 0)

    print((-1 * D[-1]))


def __starting_point():
    main()

__starting_point()

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

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

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

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

import sys


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

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

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


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

print((path[-1]))


import sys
sys.setrecursionlimit(10**7)

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

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

INF = 10 ** 40
S = [-INF] * N
S[0] = 0

def score(fst, s, C):
    for nx, p in R[fst]:
        if S[nx] >= s + p or S[nx] >= INF:
            continue
        S[nx] = s + p
        if nx in C:
            S[nx] = INF
        C[nx] = C.get(nx, 0) + 1
        score(nx, S[nx], C)
        C[nx] -= 1
        if C[nx] == 0:
            del C[nx]

score(0, 0, {0: 1})

if S[-1] < INF:
    ans = S[-1]
else:
    ans = "inf"

print(ans)


def Bellman_Ford(s, g, inf=1 << 60):
    # https://tjkendev.github.io/procon-library/python/graph/bellman-ford.html
    N = len(g)
    dist = [inf] * N
    dist[s] = 0

    for _ in range(N):
        not_updated = True
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c
                not_updated = False

        if not_updated:
            return -dist[N - 1]

    # 負閉路が存在する
    ret = dist[N - 1]
    for _ in range(N):
        not_updated = True
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c
                not_updated = False
        if not_updated: break

    if ret == dist[N - 1]:
        return -ret
    else:
        return 'inf'


def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        g[a].add((b, -c))

    ans = Bellman_Ford(s=0, g=g)
    print(ans)


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:        
        reachable[u]=True
        cnt+=1
        
  if cnt>0:
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

            if cost[to] > cost[fro] + c:
                cost[to] = cost[fro] + c
                # 頂点の数と同じ回数ループすると負の経路がある
                if i == N - 1:
                    negative[to] = True

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


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

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

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


from collections import deque
def belman(s,n,w,es):
    d = [-float("inf")] * n #d[i] : s→iの最短距離
    d[s] = 0
    c = 0
    while True:
      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
          c += 1
        if c > w:
          return 'inf'
      if not update:
        break
    return d[n-1]

def use_path(n,start,es):
    q = deque()
    chk = [False] * n
    q.append(start)
    chk[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for nex in es[node]:
            if not chk[nex]:
                chk[nex] = True
                q.append(nex)
                used.add(nex)
    return used

n,w = map(int,input().split())
es = []
l = [[] for i in range(n)]
r = [[] for i in range(n)]

for i in range(w):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    r[b].append(a)
    es.append((a,b,c))

use = use_path(n,0,l) & use_path(n,n-1,r)
ess = [(a,b,c) for a,b,c in es if a in use and b in use]
print(belman(0,n,w*2,ess))

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


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


def __starting_point():
    resolve()
__starting_point()

import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def BellmanFord(V: int, es: list, source=0):
	INF = float("inf")
	D = [INF] * V
	D[source] = 0
	for _ in range(V):
		upd = False
		for f, t, c in es:
			tmp = D[f] + c
			if D[t] > tmp:
				D[t] = tmp
				upd = True
		if not upd:
			return D[-1]
	else:
		# Negative Cycle
		return None


def main():
	N, M, *L = map(int, open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	tmp = []
	for a, b, c in zip(*[iter(L)] * 3):
		fwd[a - 1].append(b - 1)
		bwd[b - 1].append(a - 1)
		tmp += [(a - 1, b - 1, - c)]
	ra = reachable(fwd, 0) & reachable(bwd, N - 1)
	ans = BellmanFord(N, [(a, b, c) for a, b, c in tmp if a in ra and b in ra])
	if ans == None:
		print("inf")
	else:
		print(-ans)


def __starting_point():
	main()
__starting_point()

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

# Bellman-Ford
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]))
    return

print("inf")


n, m = map( int, input().split() )
edge_list = []
for _ in range( m ):
    a_i, b_i, c_i = map( int, input().split() )
    edge_list.append( ( a_i - 1, b_i - 1, - c_i ) )

INF = 10 ** 13
cost = [ INF ] * n
cost[ 0 ] = 0

NegativeLoopExist = False
for i in range( n ):
    for j in range( m ):
        a, b, c = edge_list[ j ]
        if cost[ a ] != INF and cost[ b ] > cost[ a ] + c:
            cost[ b ] = cost[ a ] + c
            if i == n - 1 and b == n - 1:
                NegativeLoopExist = True

if NegativeLoopExist:
    print( "inf" )
else:
    print( - cost[ n - 1 ] )

import sys
input = sys.stdin.readline

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

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

def __starting_point():
    main()
__starting_point()

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)

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

dist = [float('inf')]*n
dist[0] = 0
for i in range(n-1): # なぜ？
    for st, en , score in edges:
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score

negative = [False] * n

for loop in range(n):
    for e in edges:
        st, en, score = e
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score
            negative[en] = True
        if negative[st]:
            negative[en] = True

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

import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    pass


def __starting_point():
    main()


def bellman_ford(edges, N, start, goal):
    dist = [float("inf") for _ in range(N)]
    dist[start] = 0

    # 辺の情報を見ることを1ループとすると
    # 最低でも1つの頂点について，スタートからの最短距離が求まる
    # つまり，スタートからの距離は，スタートを除いた頂点の数である
    # (N-1)回のループで求まる．
    for i in range(N * 2):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] + cost:
                dist[to] = dist[fro] + cost
                # N回目に頂点の更新があると，負の経路がある
                if i == N - 1:
                    dist[to] = -float("inf")

    return -dist[goal]


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

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

cost = [float("inf") for _ in range(N)]
start = 0
goal = N - 1
ans = bellman_ford(edges, N, start, goal)
if ans == float("inf"):
    print(ans)
else:
    print(ans)

__starting_point()

def bellman(s,n,es):
    INF = float("inf")
    d = [INF] * n
    d[s] = 0
    for _ in range(n-1):
        for p,q,r in es:
            if d[p] != INF and d[q] > d[p] + r:
                d[q] = d[p] + r

    for _ in range(n-1):
        for p,q,r in es:
            if d[q] > d[p] + r:
                d[q] = -INF
    return d

n,m = map(int,input().split())
g = []
for _ in range(m):
    vi,vj,w = map(int,input().split())
    g.append([vi-1,vj-1,-w])
print(-bellman(0,n,g)[-1])

import sys
INF=float('inf')
def Bellmanford(n,edges,r):
  d=[INF]*n
  d[r]=0
  for i in range(n):
    for u,v,c in edges:
      if d[u]!=INF and d[v]>d[u]+c:
        d[v]=d[u]+c
        if i==n-1 and v==n-1:
          return 'inf'
  return (-1)*d[n-1]
n,m=map(int,input().split())
edges=[0]*m
for i in range(m):
  a,b,c=map(int,input().split())
  edges[i]=(a-1,b-1,-c)
ans=Bellmanford(n,edges,0)
print(ans)

v, e = map(int, input().split())
r = 0
INF = 10 ** 18
edges = [[] for i in range(v)]
a, b, c = [], [], []
d = [INF for i in range(v)]
for _ in range(e):
    s, t, d_ = map(int, input().split())
    edges[s - 1].append((t - 1, d_ * -1))
    a.append(s - 1)
    b.append(t - 1)
    c.append(d_ * -1)
f = False
d[r] = 0
for _ in range(v):
    for u in range(v):
        if d[u] != INF:
            for to, dist in edges[u]:
                d[to] = min(d[to], d[u] + dist)
nega = [False] * v
for _ in range(v):
    for i in range(e):
        if d[a[i]] == INF:
            continue
        if d[b[i]] > d[a[i]] + c[i]:
            d[b[i]] = d[a[i]] + c[i]
            nega[b[i]] = True
        if nega[a[i]]:
            nega[b[i]] = True
if nega[-1]:
    print("inf")
else:
    print(d[-1] * -1)

import sys

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

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

import sys
input = sys.stdin.readline

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

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

def __starting_point():
    main()
__starting_point()

def bellman_ford(s):
    d = [float('inf')]*(N+1) # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    nega = [0 for i in range(N+1)]
    for i in range(N+1):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
                nega[y] += 1
        if not update:
            break
        # 負閉路が存在
        if i == N :
          d[0] = -1
    return [d,nega]

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

for _ in range(M):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([x, y, -z])

ans = bellman_ford(1)

if ans[1][-1] > 1:
  print("inf")
else:
  print(int(-ans[0][-1]))

n, m = list(map(int, input().split()))
# from, to, cost
edges = [list(map(int, input().split())) for _ in range(m)]

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

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

print((score[n]))


import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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')
                return
print(-dist[-1])

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]
# BellmanFord
# ベルマンフォード法
def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source]=0  
  #辺の緩和
  for i in range(num_v):
    for edge in edges:
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        #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]
c,d=BellmanFord(abc,n,0)
# 負の閉路にNが含まれない時はinfじゃない
if d:
  print('inf')
else:
  print(-c)

n, m = map(int, input().split())
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))
for i in range(2*n):
    for a, b, c in edge:
        if dist[a]!=NINF and dist[b] < dist[a] + c:
            dist[b] = dist[a] + c
            if i>=n-1 and b==n-1:
                print('inf')
                return
print(dist[-1])

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

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

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

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

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

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

            if not update:
                break

        return False


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

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

    nloop = bf.shortest_path()

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


def __starting_point():
    solve()

__starting_point()

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")
            return
        else:
            break

print(S[-1])

INF = 10**30
import sys
sys.setrecursionlimit(10**6)
def bellman_ford(s, t, g):
    d = [INF for _ in range(n)] # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    val_at_t = INF # 下記参照
    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
        # 負閉路が存在して、点tの値が更新され続けている場合
        if i == n-1 and val_at_t > d[t]:
            return []
        val_at_t = d[t] #点tの現在の値
    return d

n, m = list(map(int, input().split())) # n:頂点数, m:辺の数
g = []
for _ in range(m):
    x, y, z = list(map(int, input().split())) # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])
    
ans = bellman_ford(0, n-1, g)
#print(ans)
print((-ans[n-1] if ans else "inf"))


# ABC061 D - Score Attack
import sys
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]

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

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            # ベルマンフォード法の性質より、N回目に更新があるならinf
            if i == N - 1 and nn == N:
                print("inf")
                return
            cost[nn] = cost[n] + c

print(cost[N])

n,m = map(int, input().split())
from collections import defaultdict
G = defaultdict(dict)
for i in range(1,n):
    G[i+1] = {}
for i in range(m):
    a,b,c = map(int, input().split())
    G[a][b] = c
start_vertex = 1
def bellmanford(G, start_vertex):
    if start_vertex not in G:
        return -1, -1
    distances = {}
    parents   = {}
    for node in G:
        distances[node] = float('-inf')
        parents[node]   = None
    distances[start_vertex] = 0
    for _ in range(len(G)-1):
        for node in G.keys():
            for neighbor in G[node]:
                if distances[neighbor] < distances[node] + G[node][neighbor]:
                    distances[neighbor] = distances[node] + G[node][neighbor]
                    parents[neighbor]   = node
    pathnode = n
    while pathnode != start_vertex:
        for neighbor in G[pathnode]:
            if distances[neighbor] < distances[pathnode] + G[pathnode][neighbor]:
                print('inf' , flush=True)
                return -1,-1
        pathnode = parents[pathnode]
    return distances, parents
distances, parents = bellmanford(G, start_vertex)
if distances != -1:
    print(distances[n] , flush=True)


import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        reachable[u]=True
        cnt+=1
        
  if cnt>0:
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

n, m = list(map(int, input().split()))
a = [0] * m
b = [0] * m
c = [0] * m
INF = float('inf')
dist = [INF] * n
dist[0] = 0
for i in range(m):
    a[i], b[i], c[i] = list(map(int, input().split()))
    a[i] -= 1
    b[i] -= 1
    c[i] *= -1
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[n - 1]

neg = [False] * n
for loop in range(n):
    for i in range(m):
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            neg[b[i]] = True
        if neg[a[i]]:
            neg[b[i]] = True
if neg[n - 1]:
    print('inf')
else:
    print((-ans))


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

from collections import deque
ls = [deque([]) for _ in range(N)]

for i in range(M):
    a,b,c = list(map(int,input().split()))
    a,b = a-1,b-1
    ls[a].append([b,c])
cost = [-(10**10)*N]*N
cost[0] = 0

for i in range(N):
    update = False
    q = [deque(m for m in l) for l in ls]
    for j in range(N):
        if cost[j] != -(10**10)*N:
            while q[j]:
                b,c = q[j].pop()
                if cost[b] < cost[j] + c:
                    cost[b] = cost[j] + c
                    update = True
    if i == 0:
        Max = cost[N-1]
    elif i < N-1:
        Max = max(Max,cost[N-1])

if update == True and Max < cost[N-1]:
    print('inf')
else:
    print(Max)


# longest version bellman ford
N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, c))


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

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

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

import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 15

class edge:
    def __init__(self, fr, to, cost):
        self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -c))

    #負の閉路検出
    d = [0] * N
    for i in range(N):
        for e in es:
            if d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                if e.to == N-1 and i == N-1:
                    print('inf')
                    return
    #ベルマンフォードする
    d = [INF] * N
    d[0] = 0
    for _ in range(N-1):
        update = False
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                update = True
        if not update: break
    print((-d[N-1]))

    return

def __starting_point():
    main()

__starting_point()

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

class Edge:

    def __init__(self, from_node, to_node, weight):
        self.from_node = from_node
        self.to_node = to_node
        self.weight = weight


def bellman_ford(N, edges, start, goal):
    # Weight Maximization
    MIN_INF = - 10**15
    d = [MIN_INF for _ in range(N)]
    d[start] = 0
    for loop in range(N):
        updated = False
        goal_updated = False
        for edge in edges:
            new_d = edge.weight + d[edge.from_node]
            if d[edge.to_node] < new_d:
                d[edge.to_node] = new_d
                updated = True
                if edge.to_node == goal:
                    goal_updated = True
        if not updated:
            return d[goal]
        if loop == N - 1:
            if not goal_updated:
                return d[goal]
            # exists a positive loop which connected to the goal node.
            return None


def main():
    N, M = list(map(int, input().split(' ')))
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        from_node = a - 1 
        to_node = b - 1
        weight = c
        edges.append(Edge(from_node, to_node, weight))
    start, goal = 0, N - 1
    result = bellman_ford(N, edges, start, goal)
    if result is None:
        print('inf')
    else:
        print(result)


def __starting_point():
    main()

__starting_point()

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

def shortest_path(s):
    MIN = -1 * 10 ** 12
    d = [MIN] * (n + 1)
    d[s] = 0
    update = True
    cnt = 1
    tmp = MIN
    while update:
        update = False
        for a, b, c in graph:
            if d[a] != MIN and d[b] < d[a] + c:
                d[b] = d[a] + c
                update = True
        if cnt == m: tmp = d[n]
        if update and cnt == 2 * m and d[n] > tmp: return 'inf'
        if cnt == 2 * m: update = False
        cnt += 1
    return d[n]

print(shortest_path(1))

import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[a] and reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

INF = float("inf")

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

    for i in range(n):  # たかだかn-1回ループ　n回目でまだ更新できたら負閉路がある
        for u, v, c in edges:
            if dp[u] != INF and dp[u] + c < dp[v]:
                dp[v] = dp[u] + c
                if i == n-1 and v == n-1:
                    return "inf"

    return -dp[n-1]


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

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

ans = Bellmanford(N, E)

print(ans)

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

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

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

N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
dp = (N+1)*[float("inf")]
dp[1] = 0

for n in range(N):
  for a,b,c in E:
    dp[b] = min(dp[b],dp[a]-c)

x = dp[N]

for a,b,c in E:
  dp[b] = min(dp[b],dp[a]-c)

if x!=dp[N]:
  print("inf")
else:
  print(-x)