CodeEff/ECCO huggingface dataset:
# Original solution
n, m = list(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'
        cnt += 1
    return d[n]

print((shortest_path(1)))

# Optimized solution
n, m = list(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)))
# Original solution
import sys

# sys.stdin = open('d1.in')

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

score = [-10 ** 50] * n
score[0] = 0
pred = [-1] * n
for i in range(n):
    for edge, c in list(weights.items()):
        a, b = edge
        if score[b] < score[a] + c:
            score[b] = score[a] + c
            pred[b] = a
res = score[n - 1]

b = n - 1
while b != 0:
    a = pred[b]
    c = weights[(a, b)]
    if score[b] < score[a] + c:
        res = 'inf'
    b = a

print(res)


# Optimized solution
import sys

# sys.stdin = open('d1.in')

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

score = [-10 ** 50] * n
score[0] = 0
pred = [-1] * n
for i in range(n):
    for edge, c in list(weights.items()):
        a, b = edge
        if score[b] < score[a] + c:
            score[b] = score[a] + c
            pred[b] = a
res = score[n - 1]

b = n - 1
while b != 0:
    a = pred[b]
    c = weights[(a, b)]
    if score[b] < score[a] + c:
        res = 'inf'
        break
    b = a

print(res)
# Original solution
N,M = list(map(int,input().split()))
edge = [0]*M
for i in range(M):
    a,b,c=list(map(int,input().split()))
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

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

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

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

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

if d[N-1]!=ans:
    print('inf')
else:
    print((-ans))
# Original solution
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            flg = True
    if not flg:
        break
cur = n - 1
root = set()
while cur != 0:
    root.add(cur)
    cur = before_ls[cur]
root.add(0)
flg = False
for _from, _to, cost in edge_ls:
    if d[_to] < d[_from] + cost and d[_from] != -INF:
        d[_to] = d[_from] + cost
        before_ls[_from] = _to
        if _to in root:
            flg = True
if flg:
    print("inf")
else:
    print((d[-1]))

# Optimized solution
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            if i == n - 1 and _to == n-1:
                flg = True
if flg:
    print("inf")
else:
    print((d[-1]))
# Original solution
#!/usr/bin/env python3
#ABC61 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-inf for _ in range(n)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    cnt = 0
    while 1:
        cnt += 1
        update = False
        for i in range(n):
            for edge in edges:
                e_from, e_to, e_cost = edge
                if e_from != inf and dist[e_to] < dist[e_from] + e_cost:
                    dist[e_to] = dist[e_from] + e_cost
                    update = True
        if not update:
            break
        if cnt == n - 1:
            d = dist[:]
        elif cnt > n - 1:
            if d[-1] < dist[-1]:
                print('inf')
                quit()
                return
            else:
                return d[-1]
    return dist[-1]

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

ans = Bellman_Ford(edges,0)
print(ans)


# Optimized solution
#!/usr/bin/env python3
#ABC61 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,start):
    dist = [-inf for _ in range(n)]
    dist[start] = 0
    for cnt in range(n+1):
        for edge in edges:
            e_from, e_to, e_cost = edge
            if dist[e_to] < dist[e_from] + e_cost:
                dist[e_to] = dist[e_from] + e_cost
        if cnt == n - 1:
            d = dist[:]
    if d[-1] < dist[-1]:
        print('inf')
        quit()
    else:
        return d[-1]

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

ans = Bellman_Ford(edges,0)
print(ans)
# Original solution
n, m = list(map(int, input().split()))
edges = [None] * m

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

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

for i in range(n-1):
    for f, t, c in edges:
        if d[f] == INF: continue
        d[t] = min(d[t], d[f] + c)

inf_flag = [False] * n

for i in range(n):
    for f, t, c in edges:
        if d[f] == INF: continue
        if inf_flag[f] == True:
            inf_flag[t] = True
        if d[t] > d[f] + c:
            d[t] = d[f] + c
            inf_flag[t] = True

print(("inf" if inf_flag[n-1] else -d[n-1]))


# Optimized solution
INF = float("inf")

def bellman_ford(edges, n, s):
    d = [0] + [INF] * (n-1)
    for i in range(n):
        for f, t, c in edges:
            if d[f] == INF: continue
            if d[t] > d[f] + c:
                if i == n-1: d[t] = -INF
                else: d[t] = d[f] + c
    for i in range(n):
        for f, t, c in edges:
            if d[f] == INF: continue
            d[t] = min(d[t], d[f] + c)
    return d

n, m = list(map(int, input().split()))
es = [None] * m
for i in range(m):
    f, t, c = list(map(int, input().split()))
    es[i] = (f-1, t-1, -c)

d = bellman_ford(es, n, 0)
print((-d[n-1]))
# Original solution
import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = list(map(int, input().split()))
    graph[m] = (a, b, -c)

INF = 1e18
distance = [INF] * N
distance[0] = 0

count = 0
while True:
    count += 1
    update = False
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
            if b == N and count == N:
                print("inf")
                sys.exit()
    if not update:
        break

print((-distance[N - 1]))

# Optimized solution
import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = list(map(int, input().split()))
    graph[m] = (a, b, -c)

INF = 1e18
distance = [INF] * N
distance[0] = 0

for n in range(N):
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            if b == N and n == N - 1:
                print("inf")
                sys.exit()

print((-distance[N - 1]))
# Original solution
N, M = list(map(int,input().split()))
side = [[]for _ in range(N)]
for _ in range(M):
    a,b,c = list(map(int,input().split()))
    side[a-1].append([b-1,c])
node = [-float('inf')]*N
node[0] = 0
queue = [0]
nque = []
for i in range(N+5):
    while queue:
        q = queue.pop(-1)
        for a,c in side[q]:
            if node[a] < node[q]+c:
                node[a] = node[q]+c
                nque.append(a)
    queue = nque[:]
    nque = []

while queue:
    q = queue.pop(-1)
    for a,c in side[q]:
        if node[a] < node[q]+c:
            node[a] = float('inf')
            queue.append(a)

print((node[-1]))

# Optimized solution
N, M = list(map(int,input().split()))
side = [[]for _ in range(N)]
for _ in range(M):
    a,b,c = list(map(int,input().split()))
    side[a-1].append([b-1,c])
node = [-float('inf')]*N
node[0] = 0
for _ in range(N):
    for i in range(N):
        for b,c in side[i]:
            node[b] = max(node[b],node[i]+c)


for _ in range(N):
    for i in range(N):
        for b,c in side[i]:
            if node[b] < node[i]+c:
                node[b] = float('inf')
print((node[-1]))
# Original solution
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 = list(map(int, input().split()))
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = list(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]))

if __name__ == '__main__':
    main()

# Optimized solution
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 = list(map(int, input().split()))
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = list(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]))

if __name__ == '__main__':
    main()
# Original solution
import sys

inf = float('inf')

n, m = list(map(int, sys.stdin.readline().split()))
a = []
b = []
c = []
for _ in range(m):
    ai, bi, ci = list(map(int, sys.stdin.readline().split()))
    a.append(ai - 1)
    b.append(bi - 1)
    c.append(-ci)
abc = list(zip(a, b, c))

def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    res = dist[n-1]

    for _ in range(n):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    if dist[n-1] == res:
        return -res
    else:
        return 'inf'

if __name__ == '__main__':
    ans = main()
    print(ans)

# Optimized solution
import sys

inf = float('inf')

n, m = list(map(int, sys.stdin.readline().split()))
abc = []
for _ in range(m):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    abc.append((a-1, b-1, -c))

def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    for _ in range(n):
        for a, b, c in abc:
            if dist[a] + c < dist[b]:
                dist[b] = -inf

    return -dist[n-1]

if __name__ == '__main__':
    ans = main()
    print(ans)
# Original solution
from copy import deepcopy

n, m = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]

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

for i in range(n):
    for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

xcp = deepcopy(x)
prevxn = x[n]
for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

if prevxn != x[n]:
    print('inf')
else:
    print((x[n]))

# Optimized solution
from copy import deepcopy

n, m = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]

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

for i in range(n):
    for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

xcp = [i for i in x]
prevxn = x[n]
for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

if prevxn != x[n]:
    print('inf')
else:
    print((x[n]))
# Original solution
inf = float('INF')

class edge:
    def __init__(self, source, destination, weight):
        self.from_ = source
        self.to_ = destination
        self.weight = weight

    def values(self):
        return self.from_, self.to_, self.weight

def bellman_ford(edges, start, n):
    costs = [inf] * n
    predecessors = [-1] * n
    costs[start]= 0

    for _ in range(n-1):
        for u in range(n):
            for v,w in list(edges[u].items()):
                if costs[v] > costs[u] + w:
                    costs[v] = costs[u] + w
                    predecessors[v] = u

    v = n-1
    while v > 0:
        u = predecessors[v]
        if costs[v] > costs[u] + edges[u][v]:
            return 'inf'
        v = u

    return -costs[n-1]

n,m = list(map(int, input().split()))
edges = [{} for _ in range(n)]
for _ in range(m):
    a,b,c = list(map(int, input().split()))
    edges[a-1][b-1] = -c
print((bellman_ford(edges, 0, n)))


# Optimized solution

def bellman_ford(edges, start, n):
    inf = float('INF')
    costs = [inf] * n
    predecessors = [-1] * n
    costs[start]= 0

    for _ in range(n-1):
        for e in edges:
            u,v,c = e
            if costs[v] > costs[u] + c:
                costs[v] = costs[u] + c
                predecessors[v] = u

    ans = costs[-1]
    for u,v,c in edges:
        if costs[v] > costs[u] + c:
            costs[v] = costs[u] + c

    return -ans if costs[-1] == ans else 'inf'

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))
print((bellman_ford(edges, 0, n)))
# Original solution
#coding:utf-8

import sys
from collections import defaultdict

if __name__ == "__main__":
    N, M = list(map(int, input().split(" ")))

    V = set()
    E = []
    for i in range(M):
        a, b, c = list(map(int, input().split(" ")))
        V.add(a)
        V.add(b)
        E.append((a, b, -c))

    dist = defaultdict(lambda :10**20 + 1)
    pre = {}
    dist[1] = 0


    for i in range(1, len(V)):
        for edge in E:
            u = edge[0]
            v = edge[1]

            if dist[v] > dist[u] + edge[2]:
                dist[v] = dist[u] + edge[2]
                pre[v] = u

    is_cycle = False
    cycle_node = []
    for edge in E:
        u = edge[0]
        v = edge[1]
        if dist[u] + edge[2] < dist[v]:
            is_cycle = True
            cycle_node.append(u)

    is_inf = False
    if is_cycle:
        next_node = N
        route = []
        while next_node != 1:
            route.append(next_node)
            next_node = pre[N]
        route.append(1)

        for n in cycle_node:
            if n in route:
                is_inf = True
                break

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


# Optimized solution
#coding:utf-8

import sys
from collections import defaultdict

if __name__ == "__main__":
    N, M = list(map(int, input().split(" ")))

    V = set()
    E = []
    for i in range(M):
        a, b, c = list(map(int, input().split(" ")))
        V.add(a)
        V.add(b)
        E.append((a, b, -c))

    dist = defaultdict(lambda :10**20 + 1)
    pre = {}
    dist[1] = 0


    for i in range(1, len(V)):
        for edge in E:
            u = edge[0]
            v = edge[1]

            if dist[v] > dist[u] + edge[2]:
                dist[v] = dist[u] + edge[2]
                pre[v] = u

    is_cycle = False
    cycle_node = []
    for edge in E:
        u = edge[0]
        v = edge[1]
        if dist[u] + edge[2] < dist[v]:
            is_cycle = True
            cycle_node.append(u)

    is_inf = False
    if is_cycle:
        route_node = N
        while route_node != 1:
            route_node = pre[route_node]
            if route_node in cycle_node:
                is_inf = True
                break


    if is_inf:
        print ("inf")
    else:
        print((-dist[N]))
# Original solution
n, m = list(map(int, input().split()))
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = list(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')
                exit()
print((dist[-1]))

# Optimized solution
n, m = list(map(int, input().split()))
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = list(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')
                exit()
print((dist[-1]))
# Original solution
N,M = list(map(int, input().split()))

from collections import defaultdict
neighbor = defaultdict(list)
rev_neighbor = defaultdict(list)
E = []

for i in range(M):
  a,b,c = list(map(int, input().split()))
  a,b = a-1, b-1
  E += [(a,b,c)]
  neighbor[a].append(b)
  rev_neighbor[b].append(a)

def reachable_vertices(neighbor, s):
  V = set()
  V.add(s)
  stack=[s]
  while stack:
    v = stack.pop()
    for u in neighbor[v]:
      if u not in V:
        V.add(u)
        stack.append(u)
  return V

# only vertices that are reachable from 1 or N
V = reachable_vertices(neighbor, 0) & reachable_vertices(rev_neighbor, N-1)

E = [(a,b,c) for a,b,c in E if a in V or b in V]
score = defaultdict(lambda: float('-inf'))
score[0] = 0


i = 0
updated=True
while updated:
  if i == len(V):
    print('inf')
    break

  updated = False
  for a,b,w in E:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1
else:
  print((score[N-1]))

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

from collections import defaultdict
E = []

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

def reachable_vertices(neighbor, s):
  V = set()
  V.add(s)
  stack=[s]
  while stack:
    v = stack.pop()
    for u in neighbor[v]:
      if u not in V:
        V.add(u)
        stack.append(u)
  return V

def neighbor_dict(E):
  neighbor = defaultdict(list)
  for a,b,c in E:
    neighbor[a].append(b)
  return neighbor

def rev_neighbor_dict(E):
  neighbor = defaultdict(list)
  for a,b,c in E:
    neighbor[b].append(a)
  return neighbor

def degenerate_graph(V, E):
  d = {v:i for i,v in enumerate(sorted(V))}
  return len(V), [(d[a],d[b],c) for a,b,c in E if a in V and b in V]

# only vertices that are reachable from 1 or N
N,E = degenerate_graph(reachable_vertices(neighbor_dict(E), 0), E)
N,E = degenerate_graph(reachable_vertices(rev_neighbor_dict(E), N-1), E)
score = [float('-inf')]*N
score[0] = 0


i = 0
updated=True
while updated:
  if i == N:
    print('inf')
    break

  updated = False
  for a,b,w in E:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1
else:
  print((score[N-1]))