[Solution] Moving Both Hands Codeforces Solution

M. Moving Both Hands

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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≤𝑝≤𝑁$2\le p\le 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$1$ and vertex 𝑝$p$, or report if it is impossible.

Input

The first line contains two integers 𝑁$N$ and 𝑀$M$ (2≤𝑁≤105$2\le N\le {10}^5$, 0≤𝑀≤2⋅105$0\le M\le 2\cdot {10}^5$) — the number of vertices and edges in the graph.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The 𝑖$i$-th of the next 𝑀$M$ lines contains three integers 𝑈𝑖$U_i$, 𝑉𝑖$V_i$, and 𝑊𝑖$W_i$ (1≤𝑈𝑖,𝑉𝑖≤𝑁$1\le U_i,V_i\le N$, 𝑈𝑖≠𝑉𝑖$U_i\ne V_i$, 1≤𝑊𝑖≤109$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

Output a line containing 𝑁−1$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$1$ and vertex 𝑗+1$j+1$, or −1$-1$ if it is impossible.