You are on a chain of length $n$, but you can only reach other positions through portals. Using a portal takes time. Your task is to calculate the shortest time to reach each individual position, or determine if it is unreachable.
A portal consists of two sides: one side from $u$ to $v$, and the other side from $x$ to $y$. Portals are bidirectional, meaning that if you are at any position on the path from $u$ to $v$, you can use the portal to reach any position on the path from $x$ to $y$, and vice versa. You can also use a portal multiple times, meaning if you are on the path from $u$ to $v$, you can use the portal twice to reach any position on the path from $u$ to $v$.
Input
The first line contains three positive integers $n, m, s$, representing the number of nodes, the number of portals, and your starting position.
The next $m$ lines each contain 5 integers $u\ v\ x\ y\ t$, where $1 \le u, v, x, y \le n$, representing the two ends of a portal and the time it takes to use it.
Output
Output a single line containing $n$ integers, where the $i$-th integer represents the time required to travel from $s$ to $i$. If a position is unreachable, output $-1$.
Subtasks
For $100\%$ of the data, $n, m \le 10^3$ and $0 \le t \le 10^5$.
| Test Cases | $n\le$ | $m\le$ | $t=0$ |
|---|---|---|---|
| $1 \sim 3$ | $200$ | $200$ | ✓ |
| $4 \sim 6$ | |||
| $7\sim 8$ | $10^3$ | $10^3$ | ✓ |
| $9\sim 10$ |
Examples
Input 1
6 2 1 1 1 2 3 0 3 3 5 6 0
Output 1
0 0 0 -1 0 0