A game has rooms 1 .. n and one-way tunnels (a, b, x): walking from a to b adds x to your score, and x may be negative. You start in room 1 with score 0 and must end in room n (room n is always reachable from room 1). You may walk through tunnels and rooms as many times as you like.
Write high_score(n, tunnels) -> int | None returning the maximum score you can finish with, or None if the score can be made arbitrarily large. The best finite score may be negative (it can even be -1).
high_score(4, [(1, 2, 3), (2, 4, 1), (1, 3, -2), (3, 4, 7)]) # 5 (1 -> 3 -> 4)
high_score(3, [(1, 2, 1), (2, 1, 1), (2, 3, 0)]) # None (loop 1 <-> 2 forever, then leave)
high_score(3, [(1, 3, 2), (1, 2, 0), (2, 2, 5)]) # 2 (the loop at 2 can't reach room 3)
high_score(2, [(1, 2, -1)]) # -1 (a finite score of -1)
Constraints: 2 <= n <= 200, up to 1,000 tunnels, |x| <= 10^9. Scores can exceed 32 bits. Aim for about O(n · tunnels).
Show hint
This is a longest-path question on a graph that may contain cycles, which is a shortest-path question with the signs flipped, including negative edges. Be careful about which cycles matter: a score-increasing loop only makes the answer unbounded if you can reach it from room 1 and still get to room n afterwards.