output_description: 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`.
  
  * * *
input_description: 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
attempt: # -*- coding: utf-8 -*-
  
  import sys
  
  def input(): return sys.stdin.readline().strip()
  def list2d(a, b, c): return [[c] * b for i in range(a)]
  def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
  def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
  def ceil(x, y=1): return int(-(-x // y))
  def INT(): return int(input())
  def MAP(): return map(int, input().split())
  def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
  def Yes(): print('Yes')
  def No(): print('No')
  def YES(): print('YES')
  def NO(): print('NO')
  sys.setrecursionlimit(10 ** 9)
  INF = 10 ** 18
  MOD = 10 ** 9 + 7
  
  def bellman_ford(N: int, edges: list, src: int) -> list:
      """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """
  
      # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
      res = [INF] * N
      res[src] = 0
      # 各辺によるコストの置き換えを頂点数N-1回繰り返す
      for _ in range(N-1):
          for src, dest, cost in edges:
              if res[dest] > res[src] + cost:
                  res[dest] = res[src] + cost
      ans = res[N-1]
      # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
      for _ in range(N-1):
          for src, dest, cost in edges:
              if res[dest] > res[src] + cost:
                  res[dest] = res[src] + cost
      if ans != res[N-1]
          # あったら空リストを返却
          return []
      # 問題なければ頂点リストを返却
      return res
  
  N, M = MAP()
  edges = []
  for i in range(M):
      a, b, c = MAP()
      a -= 1; b -= 1
      edges.append((a, b, -c))
  
  res = bellman_ford(N, edges, 0)
  
  if res:
      print(-res[N-1])
  else:
      print('inf')
  
problem_description: 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`.
samples: [{"input": "3 3\n    1 2 4\n    2 3 3\n    1 3 5", "output": "7\n    \n\nThere are two ways to move the piece to vertex N=3:\n\n  * vertex 1 \u2192 vertex 2 \u2192 vertex 3 : score 4+3=7\n  * vertex 1 \u2192 vertex 3 : score 5\n\nThus, the maximum possible score at the end of the game is 7.\n\n* * *"}, {"input": "2 2\n    1 2 1\n    2 1 1", "output": "inf\n    \n\nIt is possible to increase the score indefinitely by alternating between\nvertex 1 and 2.\n\n* * *"}, {"input": "6 5\n    1 2 -1000000000\n    2 3 -1000000000\n    3 4 -1000000000\n    4 5 -1000000000\n    5 6 -1000000000", "output": "-5000000000"}]