你在一条长为 $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$ |