Here is the solution:
// Negate weights
edges := [(u, v, -w) for u, v, w in original_edges]
// Bellman-Ford
dist := [inf] * (n + 1)
dist[1] := 0
for round from 1 to n - 1
for (u, v, w) in edges
if dist[u] + w < dist[v] then
dist[v] := dist[u] + w
// Check for positive cycle (negative in original)
for (u, v, w) in edges
if dist[u] + w < dist[v] then
print -1 // can get infinite score
return
print -dist[n]
The core step is propagating the cycle effect to all reachable nodes using BFS after detecting which nodes improved.
This runs in time and uses space.