Problem

In a C3 AI pipeline dependency graph, each directed edge (u, v, w) means task u can trigger task v with impact score w. Given a graph, a start node, an end node, and an integer k, return the top k highest-scoring simple paths from start to end, ordered by total score descending.

A path is simple, meaning it cannot visit the same node more than once. The score of a path is the sum of its edge weights.

Formal Specification

Implement a function that takes:

• n: number of nodes labeled 0 to n - 1
• edges: list of directed edges [from_node, to_node, weight]
• start: starting node
• end: destination node
• k: number of paths to return

Return a list of up to k paths, where each path is represented as [total_score, [node0, node1, ...]].

Examples

Example 1 Input: n = 5, edges = [[0,1,3],[0,2,2],[1,3,4],[2,3,5],[3,4,1],[1,4,6]], start = 0, end = 4, k = 3 Output: [[10,[0,1,4]],[8,[0,2,3,4]],[8,[0,1,3,4]]] Explanation: The highest-scoring simple path is 0 -> 1 -> 4 with score 9? No, it is 3 + 6 = 9; the other two paths score 2 + 5 + 1 = 8 and 3 + 4 + 1 = 8. So the correct ordered output is [[9,[0,1,4]],[8,[0,2,3,4]],[8,[0,1,3,4]]].

Example 2 Input: n = 3, edges = [[0,1,2],[1,2,3],[0,2,1]], start = 0, end = 2, k = 2 Output: [[5,[0,1,2]],[1,[0,2]]] Explanation: There are exactly two simple paths from 0 to 2.

Constraints

• 1 <= n <= 15
• 0 <= len(edges) <= 60
• 0 <= from_node, to_node < n
• -10^4 <= weight <= 10^4
• 0 <= start, end < n
• 1 <= k <= 20