CSES 1673 High Score - Implementation

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 $n$.