JMC 2016-2017 模擬予選 問題5
kagamiz logo
第 16 回 日本情報オリンピック 模擬予選 5

2016年12月10日
E869120, square1001

問題
    鉄道運賃 2 (Train Fare 2)

問題

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

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

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

あなたは街 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 つの整数 Ai, Bi, Ci, Pi (1 ≦ Ai, Bi, Ci ≦ N, 1 ≦ Pi ≦ 1,000,000,000) が空白区切りで入力される.

出力

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

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

入出力例

入力例 1 入力例 2
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
  
出力例 1 出力例 2
0
2
2
10


   
0
2
2
5
5
-1
  

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

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

※各入出力例のデータは,右クリック等によりファイルに保存して利用可能です.


採点用データ

入力データ 入力1 入力2 入力3 入力4 入力5
出力データ 出力1 出力2 出力3 出力4 出力5