長さ $n$ のチェーン上にいます。あなたはいくつかのポータルを使って他の場所に移動することができます。ポータルの使用には時間がかかります。各位置について、そこに到達するための最短時間を計算してください。到達不可能な場合は $-1$ と出力してください。

ポータルは2つの端で構成されており、一方は $u$ から $v$ までの区間、もう一方は $x$ から $y$ までの区間です。ポータルは双方向です。つまり、$u$ から $v$ までの経路上のどこにいても、ポータルを使って $x$ から $y$ までの経路上のどこへでも移動でき、その逆も可能です。ポータルは複数回使用できます。つまり、$u$ から $v$ までの経路にいる場合、ポータルを2回使うことで $u$ から $v$ までの経路上のどこへでも移動できます。

入力

1行目に3つの正整数 $n, m, s$ が与えられます。これらはそれぞれノード数、ポータル数、あなたの現在地を表します。

続く $m$ 行には、それぞれ5つの整数 $u\ v\ x\ y\ t$ が与えられます。これは、ポータルの両端の区間と、移動にかかる時間 $t$ を表します。ここで $1 \le u, v, x, y \le n$ です。

出力

1行に $n$ 個の整数を出力してください。$i$ 番目の整数は $s$ から $i$ に到達するために必要な時間です。到達不可能な場合は $-1$ を出力してください。

入出力例

入力 1

6 2 1
1 1 2 3 0
3 3 5 6 0

出力 1

0 0 0 -1 0 0

小課題

すべてのデータにおいて、$n, m \le 10^3, 0 \le t \le 10^5$ を満たします。