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