你在一條長為 $n$ 的鏈上，但你只能透過一些傳送門來到達其他位置，使用一個傳送門需要時間，你的任務是計算出對於每一個單獨的位置，到達那裡需要的最短時間，或者無法到達。

一個傳送門由兩側組成，一側從 $u$ 到 $v$，另一側從 $x$ 到 $y$。傳送門是雙向的，這意味著你只要站在 $u$ 到 $v$ 的路徑中的任何一個位置，就可以透過傳送門到達 $x$ 到 $y$ 的路徑的任何一個位置，反之亦然。你也可以使用一個傳送門多次，這意味著你如果在 $u$ 到 $v$ 的路徑中，你可以傳送 2 次到達 $u$ 到 $v$ 路徑上的任何一個位置。

輸入格式

第一行三個正整數 $n, m, s$ 表示節點數、傳送門數和你所在的位置。

接下來 $m$ 行，每行 5 個整數 $u\ v\ x\ y\ t$ 滿足 $1 \le u, v, x, y \le n$，表示一組傳送門的兩端以及消耗時間。

輸出格式

輸出一行，$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

子任務

對於 $100\%$ 的資料，保證 $n, m \le 10^3, 0 \le t \le 10^5$