1663. Print the Cheapest Route Itself

An undirected graph has n vertices and m edges, every weight at least 1. Print the VERTICES of a cheapest route from vertex 1 to vertex n, in order, separated by single spaces. Print -1 if there is no route.

A graph usually has several cheapest routes, so the question is not yet well posed. It is pinned here: among all routes of smallest total weight, print the one whose SEQUENCE OF VERTEX NUMBERS is smallest in dictionary order.

4 vertices 1 - 2 (1) 2 - 4 (1) 1 - 3 (1) 3 - 4 (1) -> 1 2 4

Both 1 2 4 and 1 3 4 cost 2. The first is smaller in dictionary order because 2 comes before 3.

## The four things that have to be said

directed? no. Every edge may be walked either way. self-loops? allowed, and never on a cheapest route, since a weight is at least 1. parallel edges? allowed, at different weights, and the cheaper copy decides the cost while the vertex sequence is the same either way. unreachable? yes. Print -1. When n is 1 the answer is the single line "1", a route of no edges at all.

## Why weights of at least 1 are part of the question

If an edge could weigh 0 the dictionary-smallest cheapest route would not exist. On a zero-weight edge 1 - 2 with a zero-weight route onward, 1 2 5 is beaten by 1 2 1 2 5, which is beaten by 1 2 1 2 1 2 5, forever, because a smaller number keeps appearing earlier. Positive weights make every cheapest route simple, so there are finitely many and a smallest one exists.

## What most people try first

Run Dijkstra, record parent[v] whenever dist[v] improves, then follow parents back from n. That prints A cheapest route and it is the standard answer, but it prints whichever one the heap happened to settle, which is not a defined answer to this question. Two correct programs disagree, which is the real problem with unpinned route questions.

Trying to fix it by preferring the smaller parent during relaxation does not work either. The parent that is smallest locally may sit on a route that is not extendable to n at the optimal cost, and by the time that is discovered the choice has already been written.

## Distances TO the target, then walk forwards

Run Dijkstra from vertex n instead of from vertex 1, giving distT[v], the cheapest cost from v to n. Then walk forwards:

u = 1, print u while u != n: among edges (u, v, w) with w + distT[v] == distT[u], take the SMALLEST v print v, u = v

## Why that is exactly the dictionary minimum

An edge satisfying w + distT[v] == distT[u] is one that can still be completed to n at the optimal remaining cost, so every such choice keeps the route optimal. The set of optimal routes through a given prefix is therefore decided only by that prefix's last vertex, which means the smallest legal next vertex at each step is also the smallest overall: no later choice can compensate for a larger number earlier.

The walk terminates because distT strictly decreases at every step, since w >= 1, so no vertex can appear twice.

Forward distances alone cannot do this. dist[v] == dist[u] + w says only that v is reached optimally, not that it leads anywhere useful, so a greedy walk on them can leave the set of routes that reach n cheaply.

## Overflow, computed rather than assumed

A cheapest route is simple, so it uses at most n - 1 = 49999 edges of up to 10^9, and a total can reach about 5 * 10^13. That is far past the 2147483647 a signed 32 bit integer holds, so the distances need 64 bits. One weight of 10^9 fits in 32 bits comfortably.

## Cost

O(m log n) for the search and O(m) for the walk, which rescans each visited vertex's edge list once.

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000`