Negate weights and run Bellman-Ford:
dist = array of size n + 1, all infinity
dist[1] = 0
for round from 1 to n - 1:
for (u, v, w) in edges:
if dist[u] + (-w) < dist[v]:
dist[v] = dist[u] + (-w)
inCycle = array of size n + 1, all false
for (u, v, w) in edges:
if dist[u] + (-w) < dist[v]:
mark v and all reachable nodes as inCycle
if inCycle[n] and n is reachable from 1:
print -1
else:
print -dist[n]
Check if a negative cycle can affect the path to node .