Вы находитесь на цепи длиной $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$-е число обозначает минимальное время, необходимое для достижения позиции $i$ из $s$. Если достичь позиции невозможно, выведите $-1$.

Примеры

Пример 1

Входные данные

6 2 1
1 1 2 3 0
3 3 5 6 0

Выходные данные

0 0 0 -1 0 0

Подзадачи

Для $100\%$ данных гарантируется, что $n, m \le 10^3, 0 \le t \le 10^5$.