K - Planning Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 6 点

問題文

N 頂点 M 辺の重み付き有向グラフが与えられます。

頂点には 1 から N までの番号が振られています。
また、i\ (1 \leq i \leq M) 本目の辺は頂点 u_i から頂点 v_i に向けて張られており、その重みは w_i です。

k=1,2,\ldots,N について、以下の問題を解いてください。

  • 頂点 1 から始めて頂点 k を一度以上通り、頂点 N まで行く経路が存在するか判定し、存在するならそのうち最短のものの長さを出力せよ。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq u_i,v_i \leq N
  • u_i \neq v_i
  • 1 \leq w_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1 w_1
u_2 v_2 w_2
\hspace{0.8cm}\vdots
u_M v_M w_M

出力

N 行にわたって出力せよ。i\ (1 \leq i \leq N) 行目には k=i の場合の答えを以下に従って出力すること。

  • 頂点 1 から始めて頂点 k を一度以上通り、頂点 N まで行く経路が存在するなら、そのうち最短のものの長さを出力。
  • 頂点 1 から始めて頂点 k を一度以上通り、頂点 N まで行く経路が存在しないなら -1 を出力。

入力例 1

3 3
1 2 3
2 3 4
1 3 2

出力例 1

2
7
2
  • k=1 のとき、3 本目の辺を通って直接頂点 3 に移動する経路が最短です。
  • k=2 のとき、1 本目の辺を通って頂点 2 に移動したあと 2 本目の辺を通って頂点 3 に移動する経路が最短です。
  • k=3 のとき、3 本目の辺を通って直接頂点 3 に移動する経路が最短です。

入力例 2

5 10
2 1 1
2 5 5
1 2 6
2 5 4
5 3 2
1 3 1
1 3 4
3 5 4
1 5 3
5 2 3

出力例 2

3
10
5
-1
3

Score : 6 points

Problem Statement

You are given a weighted directed graph with N vertices and M edges.

The vertices are numbered 1 to N.
The i-th edge (1 \leq i \leq M) goes from Vertex u_i to Vertex v_i and has a weight of w_i.

For each k=1,2,\ldots,N, solve the problem below.

  • Determine whether there is a path that starts at Vertex 1, visits Vertex k one or more times, and ends at Vertex N. If it exists, print the shortest possible length of such a path.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq u_i,v_i \leq N
  • u_i \neq v_i
  • 1 \leq w_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1 w_1
u_2 v_2 w_2
\hspace{0.8cm}\vdots
u_M v_M w_M

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the answer for the case k=i, as follows.

  • If there is a path that starts at Vertex 1, visits Vertex k one or more times, and ends at Vertex N, print the shortest possible length of such a path.
  • If there is no path that starts at Vertex 1, visits Vertex k one or more times, and ends at Vertex N, print -1.

Sample Input 1

3 3
1 2 3
2 3 4
1 3 2

Sample Output 1

2
7
2
  • For k=1, the shortest path traverses the 3-rd edge to reach Vertex 3 directly.
  • For k=2, the shortest path first traverses the 1-rd edge to get to Vertex 2 and then traverses the 2-nd edge to reach Vertex 3.
  • For k=3, the shortest path traverses the 3-rd edge to reach Vertex 3 directly.

Sample Input 2

5 10
2 1 1
2 5 5
1 2 6
2 5 4
5 3 2
1 3 1
1 3 4
3 5 4
1 5 3
5 2 3

Sample Output 2

3
10
5
-1
3