Given n nodes numbered 0 .. n-1 and a list edges of triples [u, v, w] meaning a directed edge from u to v of positive weight w, return the maximum total weight of any path in the graph. A path may start and end anywhere; a path consisting of a single node has weight 0.
If the graph contains a cycle, return -1.
Examples
Input: n = 4, edges = [[0, 1, 3], [1, 2, 4], [0, 2, 10], [2, 3, 1]]
Output: 11
Explanation: 0 -> 2 -> 3 weighs 10 + 1 = 11.
Input: n = 2, edges = []
Output: 0
Input: n = 3, edges = [[0, 1, 1], [1, 2, 1], [2, 0, 1]]
Output: -1
Constraints
1 <= n <= 10**4,0 <= len(edges) <= 3 * 10**4,1 <= w <= 10**6- Target: O(V + E) time.
Goals
- Relax edges in topological order to compute a longest path
- Detect that the input is not a DAG and report it