Maximum Walk Score

You are given a directed graph with n nodes labeled 1 to n and an array edges, where edges[i] = [a, b, x] is a one-way edge from node a to node b carrying a score value x (which may be negative). Self-loops and multiple edges between the same pair of nodes may occur.

A walk starts at node 1 with total score 0, follows edges one at a time (the same edge may be used any number of times), and ends at node n. Each traversal of an edge adds its value x to the total.

Return the maximum total score a walk can achieve. If the total can be made arbitrarily large, return -1.

It is guaranteed that node n is reachable from node 1.

Examples

Example 1

Input: n = 4, edges = [[1,2,3],[2,4,-1],[1,3,-2],[3,4,7],[1,4,4]]
Output: 5
Explanation: The walk 1 -> 3 -> 4 scores -2 + 7 = 5. The alternatives score 3 + (-1) = 2 and 4, so 5 is the maximum.

Example 2

Input: n = 4, edges = [[1,2,5],[2,3,3],[3,2,4],[3,4,1]]
Output: -1
Explanation: The cycle 2 -> 3 -> 2 gains 3 + 4 = 7 per lap and lies on a route from node 1 to node 4, so the total can be made arbitrarily large.