你在一條長為 $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$
| 測試點 | $n\le$ | $m\le$ | $t=0$ |
|---|---|---|---|
| $1 \sim 3$ | $200$ | $200$ | ✓ |
| $4 \sim 6$ | |||
| $7\sim 8$ | $10^3$ | $10^3$ | ✓ |
| $9\sim 10$ |