Print Shortest Path

Given a positive-weight undirected graph with n vertices numbered 1 through n and m edge occurrences, return any shortest route from vertex 1 to vertex n. If…

Given a positive-weight undirected graph with n vertices numbered 1 through n and m edge occurrences, return any shortest route from vertex 1 to vertex n. If reachable, return [cost, 1, ..., n]: the first element is the total weight and the remaining elements are vertices in route order. If unreachable, return exactly [-1]. Different optimal routes are equally valid. Each edge [u, v, weight] works in both directions. Positive loops and parallel occurrences are explicitly supported by this local contract; this is not an extra guarantee attributed to the publisher. Do not mutate edges. The supplied m must equal edges.length.

2 ≤ n ≤ 10000. 0 ≤ m ≤ 20000 and m = edges.length. 1 ≤ u, v ≤ n and 1 ≤ weight ≤ 100000. The answer may contain n + 1 = 10001 integers. Its cost is at most (n - 1) × 100000 = 999900000. Visualization uses at most 12 vertices, 24 edge occurrences and weights through 10000. These visual-only bounds do not narrow coding input or output.

Example 1: input n = 5, m = 6, edges = [[1,2,2],[2,5,5],[2,3,4],[1,4,1],[4,3,3],[3,5,1]]; output [5,1,4,3,5]. Route 1→4→3→5 has cost 1 + 3 + 1 = 5.

Example 2: input n = 4, m = 4, edges = [[1,2,2],[2,3,4],[1,4,1],[4,3,3]]; output [1,1,4]. The direct edge from 1 to 4 costs only 1.

Category: Graphs. Topic: graph. Difficulty: Hard. Patterns: graph-traversal.