0590 - 鉄道運賃 2 (Train Fare 2)

問題

JOI 国には N 個の街があり, それぞれ 1, 2, ..., N の番号が付けられている. また JOI 国には M 本の鉄道があり, それぞれの鉄道には 1, 2, ..., M の番号が付けられている.

i (1 ≤ i ≤ M) 本目の鉄道は, 街 A_i, 街 B_i, 街 C_i という 3 つの街を双方向に走っている. この鉄道の運賃は, 乗り始めと乗り終わる街を問わず P_i 円である.

今日は JOI 国で鉄道感謝祭という割引セールが開催されている. このセールの内容は以下の様なものである.

• 街 s から鉄道に乗り始め, 街 t で鉄道から降りるとき, 途中で運賃が Q₁, Q₂, ..., Q_m (m は経由した鉄道の種類数）の鉄道を経由した場合, Q₁, Q₂, Q₃, ..., Q_m の最大値が s から t まで行くのにかかる値段となる.

あなたは街 s に住んでいるので, このセールによって街 s から他の街に行くのにかかる最小の値段がいくらであるかが気になった. 街 s から他の街に行くために必要な値段の最小値を, それぞれの街について求めよ.

入力

入力は M + 1 行からなる.

1 行目に, 3 つの整数 N, M, s (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ s ≤ N) が空白区切りで与えられる.

1 + i 行目 (1 ≤ i ≤ M) には, 4 つの整数 A_i, B_i, C_i, P_i (1 ≤ A_i, B_i, C_i ≤ N, 1 ≤ P_i ≤ 1,000,000,000) が空白区切りで入力される.

出力

d(i, j) を街 i から j まで行くための最短コストとする. ただし, 街 i から街 j に鉄道を乗り継いで行くことが不可能である場合, d(i, j) = -1 とする.

このとき, i 行目 (1 ≤ i ≤ N) に d(s, i) を出力せよ.

入出力例

4 2 1
1 2 3 2
2 3 4 10

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

0
2
2
10

0
2
2
5
5
-1

入力例 1 では,　以下のようになる.

• d(1, 1) : 最初から街 1 にいるので値段は 0 円.
• d(1, 2) : 鉄道 1 を使うと 2 円.
• d(1, 3) : 鉄道 1 を使うと 2 円.
• d(1, 4) : 鉄道 1 を使い, その後街 2 もしくは街 3 で乗り換えて鉄道 2 を使うと, 鉄道 1 の運賃 2 円と鉄道 2 の運賃 10 円のうち, 高い方である 10 円.

入力例 2 では,　以下のようになる.

• d(1, 1) : 最初から街 1 にいるので値段は 0 円.
• d(1, 2) : 鉄道 1 を使うと 2 円.
• d(1, 3) : 鉄道 1 を使うと 2 円.
• d(1, 4) : 鉄道 1 を使い, その後街 3 で乗り換えて鉄道 3 を使うと, 鉄道 1 の運賃 2 円と鉄道 3 の運賃 5 円のうち, 高い方である 5 円.
• d(1, 5) : 鉄道 1 を使い, その後街 3 で乗り換えて鉄道 3 を使うと, 鉄道 1 の運賃 2 円と鉄道 3 の運賃 5 円のうち, 高い方である 5 円.
• d(1, 6) : どのようにしても街 1 から街 6 にはたどり着けないので, -1.