Moving Both Hands
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1800
Tags: dp, graphs, shortest paths

Pak Chanek is playing one of his favourite board games. In the game, there is a directed graph with $$$N$$$ vertices and $$$M$$$ edges. In the graph, edge $$$i$$$ connects two different vertices $$$U_i$$$ and $$$V_i$$$ with a length of $$$W_i$$$. By using the $$$i$$$-th edge, something can move from $$$U_i$$$ to $$$V_i$$$, but not from $$$V_i$$$ to $$$U_i$$$.

To play this game, initially Pak Chanek must place both of his hands onto two different vertices. In one move, he can move one of his hands to another vertex using an edge. To move a hand from vertex $$$U_i$$$ to vertex $$$V_i$$$, Pak Chanek needs a time of $$$W_i$$$ seconds. Note that Pak Chanek can only move one hand at a time. This game ends when both of Pak Chanek's hands are on the same vertex.

Pak Chanek has several questions. For each $$$p$$$ satisfying $$$2 \leq p \leq N$$$, you need to find the minimum time in seconds needed for Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex $$$1$$$ and vertex $$$p$$$, or report if it is impossible.

Input format:
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 10^5$$$, $$$0 \leq M \leq 2 \cdot 10^5$$$) — the number of vertices and edges in the graph.

The $$$i$$$-th of the next $$$M$$$ lines contains three integers $$$U_i$$$, $$$V_i$$$, and $$$W_i$$$ ($$$1 \le U_i, V_i \le N$$$, $$$U_i \neq V_i$$$, $$$1 \le W_i \le 10^9$$$) — a directed edge that connects two different vertices $$$U_i$$$ and $$$V_i$$$ with a length of $$$W_i$$$. There is no pair of different edges $$$i$$$ and $$$j$$$ such that $$$U_i = U_j$$$ and $$$V_i = V_j$$$.

Output format:
Output a line containing $$$N-1$$$ integers. The $$$j$$$-th integer represents the minimum time in seconds needed by Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex $$$1$$$ and vertex $$$j+1$$$, or $$$-1$$$ if it is impossible.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
If initially Pak Chanek's left hand is on vertex $$$1$$$ and his right hand is on vertex $$$5$$$, Pak Chanek can do the following moves:

1. Move his right hand to vertex $$$4$$$ in $$$1$$$ second.
2. Move his left hand to vertex $$$2$$$ in $$$2$$$ seconds.
3. Move his left hand to vertex $$$4$$$ in $$$1$$$ second.

In total it needs $$$1+2+1=4$$$ seconds. It can be proven that there is no other way that is faster.

Example input:
5 7
1 2 2
2 4 1
4 1 4
2 5 3
5 4 1
5 2 4
2 1 1

Example output:
1 -1 3 4

Editorial:
Suppose we are trying to find out the minimum time to get the hands from vertices $$$1$$$ and $$$k$$$ to the same vertex. If both hands end up on some vertex $$$v$$$, then the time required is $$$d(1,v) + d(k,v)$$$, with $$$d(x,y)$$$ being the minimum distance to go from vertex $$$x$$$ to $$$y$$$.
Suppose $$$d'(x,y)$$$ is the minimum distance to go from vertex $$$x$$$ to $$$y$$$ in the reversed graph (i.e. all edges' directions are reversed). Then $$$d(1,v) + d(k,v) = d(1,v) + d'(v,k)$$$.
The minimum time if both hands are initially on vertices $$$1$$$ and $$$k$$$ is the minimum value of $$$d(1,v) + d'(v,k)$$$ for all vertices $$$v$$$. This is the same as the minimum distance to go from vertex $$$1$$$ to $$$k$$$ where in the middle of our path, we can reverse the graph at most once.
Therefore we can set up a graph like the following:
• Each vertex is a pair $$$(x,b)$$$, where $$$x$$$ is a vertex in the original graph and $$$b$$$ is a boolean determining whether we have already reversed the graph or not.
• For each edge $$$i$$$ in the original graph, there is an edge from $$$(U_i, 0)$$$ to $$$(V_i, 0)$$$ and an edge from $$$(V_i, 1)$$$ to $$$(U_i, 1)$$$, both with weight $$$W_i$$$.
• For each vertex $$$x$$$ in the original graph, there is a edge from $$$(x,0)$$$ to $$$(x,1)$$$ with weight $$$0$$$.
After this, we do the Dijkstra algorithm once on the new graph from vertex $$$(1, 0)$$$. Then, the optimal time if both hands start from vertices $$$1$$$ and $$$k$$$ in the original graph is equal to $$$d((1,0), (k,1))$$$ in the new graph.
Time complexity: $$$O(N+M \log M)$$$