비행기 타고 가요

정보과학을 잘하는 사람만 거주할 수 있다는 국가, '경곽국'을 아는가? 경곽국은 총 $N$개의 도시로 이루어져 있으며, 각각 1번부터 $N$번까지 번호가 붙어 있다.

경곽국에서 도시 사이를 이동하는 수단은 비행기뿐이다. 모든 도시쌍에 대하여 그 두 도시 사이를 경유하는 비행기가 존재한다. 다만, 비행기를 타려면 '비행기 표'가 필요하다. 경곽국에서 구매할 수 있는 비행기 표는 총 $M$개이며, 각각 1번부터 $M$번까지 번호가 붙어 있다. $i$번 표의 가격은 $A_i$원이고, 출발 도시의 번호가 $B_i$ 이상 $C_i$ 이하이고 도착 도시의 번호가 $D_i$ 이상 $E_i$ 이하일 때에만 사용할 수 있다 ($1 \le i \le M$).

모든 $M$개의 표는 일회용이며 한 번만 구매할 수 있다.

교준이의 집은 $K$번 도시에 있다. 현재 교준이는 집에서 놀고 있다.

교준이가 집을 나와 $X$번 도시로 가기 위해 구매해야 하는 표 값의 합의 최솟값을 $W_X$라 하자 ($1 \le X \le N$). 단, 교준이는 집을 나오기 전에 필요한 모든 비행기 표를 구매한다. 어떻게 표를 사서 이동하더라도 $X$번 도시로 갈 수 없다면 $W_X = -1$로 정의한다.

$W_1, \cdots, W_N$의 값을 모두 구하는 프로그램을 작성하시오.

첫 번째 줄에 도시의 개수 $N$, 비행기 표의 총 개수 $M$, 교준이의 집이 있는 도시의 번호 $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$개의 줄에 걸쳐 비행기 표의 정보가 주어진다. $(i+1)$번째 줄에는 $i$번 표의 정보인 다섯 정수 $A_i$, $B_i$, $C_i$, $D_i$, $E_i$가 공백으로 구분되어 주어진다 ($1 \le i \le M$).

첫 번째 줄에 $N$개의 정수 $W_1, \cdots, W_N$을 공백으로 구분하여 차례대로 출력한다.

$W_K = 0$임에 유의하라.

• $1 \le N \le 250{,}000$
• $1 \le M \le 250{,}000$
• $1 \le K \le N$
• $0 \le A_i \le 10^9$ ($1 \le i \le M$)
• $1 \le B_i \le C_i \le N$ ($1 \le i \le M$)
• $1 \le D_i \le E_i \le N$ ($1 \le i \le M$)